[알고리즘] 그래프

// chap06_graph 전체 구현 + 입력 방식 2종류 (직접 addEdge vs 파일 입력)
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <limits>
#include <cstring>
#include <fstream>
using namespace std;

const int INF = 1e9; // 무한대 값 정의

//--------------------------------------
// 1. 인접행렬 표현
class GraphMatrix {
public:
    int n; // 정점 수
    vector<vector<int>> adj;

    GraphMatrix(int size) : n(size), adj(n, vector<int>(n, 0)) {}

    void addEdge(int u, int v) {
        adj[u][v] = 1; // 방향 그래프
        adj[v][u] = 1; // 무방향이면 이 줄 유지
    }
};

//--------------------------------------
// 2. 인접리스트 표현
class GraphList {
public:
    int n;
    vector<vector<int>> adj;

    GraphList(int size) : n(size), adj(n) {}

    void addEdge(int u, int v, bool directed = false) {
        adj[u].push_back(v);
        if (!directed)
            adj[v].push_back(u);
    }

    // 파일로부터 에지 추가: 파일 형식 "정점수 에지수" 후 "u v" 형식의 간선 나열
    void loadFromFile(const string& filename, bool directed = false) {
        ifstream in(filename);
        if (!in) {
            cerr << "파일 열기 실패: " << filename << endl;
            return;
        }
        int u, v, nodeCount, edgeCount;
        in >> nodeCount >> edgeCount;
        n = nodeCount;
        adj.assign(n, vector<int>());
        while (in >> u >> v) {
            addEdge(u, v, directed);
        }
        in.close();
    }
};

//--------------------------------------
// 3. 가중치 그래프 인접행렬 표현
class WeightedGraphMatrix {
public:
    int n;
    vector<vector<int>> weight;

    WeightedGraphMatrix(int size) : n(size), weight(n, vector<int>(n, INF)) {
        for (int i = 0; i < n; ++i)
            weight[i][i] = 0; // 자기 자신으로 가는 비용은 0
    }

    void addEdge(int u, int v, int w) {
        weight[u][v] = w; // 방향 그래프
        // weight[v][u] = w; // 무방향이면 포함
    }
};

//--------------------------------------
// 4. BFS (너비우선탐색)
void BFS(const vector<vector<int>>& adj, int start) {
    int n = adj.size();
    vector<bool> visited(n, false);
    queue<int> q;

    q.push(start);
    visited[start] = true;

    cout << "BFS 순회: ";
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        cout << cur << " ";
        for (int next : adj[cur]) {
            if (!visited[next]) {
                visited[next] = true;
                q.push(next);
            }
        }
    }
    cout << "\n";
}

//--------------------------------------
// 5. DFS (재귀)
void DFS_recursive(const vector<vector<int>>& adj, int v, vector<bool>& visited) {
    visited[v] = true;
    cout << v << " ";
    for (int next : adj[v]) {
        if (!visited[next])
            DFS_recursive(adj, next, visited);
    }
}

void DFS(const vector<vector<int>>& adj, int start) {
    int n = adj.size();
    vector<bool> visited(n, false);
    cout << "DFS 순회: ";
    DFS_recursive(adj, start, visited);
    cout << "\n";
}

//--------------------------------------
// 6. 연결 요소 개수 구하기 (DFS)
int countConnectedComponents(const vector<vector<int>>& adj) {
    int n = adj.size(), count = 0;
    vector<bool> visited(n, false);
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            DFS_recursive(adj, i, visited);
            count++;
        }
    }
    return count;
}

//--------------------------------------
// 7. 두 노드 간 경로 존재 여부 (BFS)
bool pathExists(const vector<vector<int>>& adj, int u, int v) {
    int n = adj.size();
    vector<bool> visited(n, false);
    queue<int> q;
    q.push(u);
    visited[u] = true;
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        if (cur == v) return true;
        for (int next : adj[cur]) {
            if (!visited[next]) {
                visited[next] = true;
                q.push(next);
            }
        }
    }
    return false;
}

//--------------------------------------
// main 함수 예시 실행
int main() {
    // 방법 1: 수동 addEdge로 그래프 생성
    GraphList g(8);
    g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3);
    g.addEdge(2, 4); g.addEdge(3, 5); g.addEdge(4, 5);

    BFS(g.adj, 0);
    DFS(g.adj, 0);

    cout << "연결 요소 수: " << countConnectedComponents(g.adj) << "\n";
    cout << "0과 5 사이 경로 존재? " << (pathExists(g.adj, 0, 5) ? "Yes" : "No") << "\n";

    // 방법 2: 파일로부터 그래프 입력 (예: input.txt)
    GraphList g2(0);
    g2.loadFromFile("graph_input.txt");
    BFS(g2.adj, 0);
    DFS(g2.adj, 0);

    return 0;
}

 

이제 각각의 코드를 구현하면

 

// chap06_graph 전체 구현 + 입력 방식 2종류 (직접 addEdge vs 파일 입력)
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <limits>
#include <cstring>
#include <fstream>
using namespace std;

const int INF = 1e9; // 무한대 값 정의

//--------------------------------------
// 1. 인접행렬 표현
// 사용 예: GraphMatrix mat(6); mat.addEdge(0,1); mat.printMatrix();
class GraphMatrix {
public:
    int n; // 정점 수
    vector<vector<int>> adj;

    GraphMatrix(int size) : n(size), adj(n, vector<int>(n, 0)) {}

    void addEdge(int u, int v) {
        adj[u][v] = 1; // 방향 그래프
        adj[v][u] = 1; // 무방향이면 이 줄 유지
    }

    void printMatrix() {
        cout << "\n[인접행렬] 무방향 그래프 출력:\n";
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cout << adj[i][j] << " ";
            }
            cout << "\n";
        }
    }
};

//--------------------------------------
// 2. 인접리스트 표현 + 파일 입력 기능
// 사용 예:
//  - 수동: g.addEdge(0,1);
//  - 파일: g.loadFromFile("graph_input.txt");
class GraphList {
public:
    int n;
    vector<vector<int>> adj;

    GraphList(int size) : n(size), adj(n) {}

    void addEdge(int u, int v, bool directed = false) {
        adj[u].push_back(v);
        if (!directed)
            adj[v].push_back(u);
    }

    // 파일 형식: 첫 줄 "정점수 간선수", 이후 각 줄 "u v"
    void loadFromFile(const string& filename, bool directed = false) {
        ifstream in(filename);
        if (!in) {
            cerr << "파일 열기 실패: " << filename << endl;
            return;
        }
        int u, v, nodeCount, edgeCount;
        in >> nodeCount >> edgeCount;
        n = nodeCount;
        adj.assign(n, vector<int>());
        while (in >> u >> v) {
            addEdge(u, v, directed);
        }
        in.close();
    }
};

//--------------------------------------
// 3. 가중치 그래프 인접행렬 표현
// 사용 예: WeightedGraphMatrix wg(4); wg.addEdge(0,1,5);
class WeightedGraphMatrix {
public:
    int n;
    vector<vector<int>> weight;

    WeightedGraphMatrix(int size) : n(size), weight(n, vector<int>(n, INF)) {
        for (int i = 0; i < n; ++i)
            weight[i][i] = 0; // 자기 자신으로 가는 비용은 0
    }

    void addEdge(int u, int v, int w) {
        weight[u][v] = w;
        // 무방향 그래프의 경우 다음 줄도 포함:
        // weight[v][u] = w;
    }
};

//--------------------------------------
// 4. BFS: 너비우선탐색
// 실행 예: BFS(g.adj, 0);
void BFS(const vector<vector<int>>& adj, int start) {
    int n = adj.size();
    vector<bool> visited(n, false);
    queue<int> q;

    q.push(start);
    visited[start] = true;

    cout << "BFS 순회 (시작 노드: " << start << "): ";
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        cout << cur << " ";
        for (int next : adj[cur]) {
            if (!visited[next]) {
                visited[next] = true;
                q.push(next);
            }
        }
    }
    cout << "\n";
}

//--------------------------------------
// 5. DFS: 깊이우선탐색
// 실행 예: DFS(g.adj, 0);
void DFS_recursive(const vector<vector<int>>& adj, int v, vector<bool>& visited) {
    visited[v] = true;
    cout << v << " ";
    for (int next : adj[v]) {
        if (!visited[next])
            DFS_recursive(adj, next, visited);
    }
}

void DFS(const vector<vector<int>>& adj, int start) {
    int n = adj.size();
    vector<bool> visited(n, false);
    cout << "DFS 순회 (시작 노드: " << start << "): ";
    DFS_recursive(adj, start, visited);
    cout << "\n";
}

//--------------------------------------
// 6. 연결 요소 개수 구하기
// 실행 예: int components = countConnectedComponents(g.adj);
int countConnectedComponents(const vector<vector<int>>& adj) {
    int n = adj.size(), count = 0;
    vector<bool> visited(n, false);
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            DFS_recursive(adj, i, visited);
            count++;
        }
    }
    return count;
}

//--------------------------------------
// 7. 두 노드 간 경로 존재 여부
// 실행 예: bool found = pathExists(g.adj, 0, 5);
bool pathExists(const vector<vector<int>>& adj, int u, int v) {
    int n = adj.size();
    vector<bool> visited(n, false);
    queue<int> q;
    q.push(u);
    visited[u] = true;
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        if (cur == v) return true;
        for (int next : adj[cur]) {
            if (!visited[next]) {
                visited[next] = true;
                q.push(next);
            }
        }
    }
    return false;
}

//--------------------------------------
// main 함수 예시 실행
int main() {
    // [1] 인접행렬 예제 실행
    GraphMatrix mat(6);
    mat.addEdge(0, 1);
    mat.addEdge(0, 2);
    mat.addEdge(1, 2);
    mat.addEdge(1, 3);
    mat.addEdge(2, 4);
    mat.addEdge(4, 5);
    mat.printMatrix();

    // [2~5] 수동 방식으로 그래프 구성 후 BFS, DFS
    GraphList g(8);
    g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3);
    g.addEdge(2, 4); g.addEdge(3, 5); g.addEdge(4, 5);

    BFS(g.adj, 0);   // [4] BFS 실행
    DFS(g.adj, 0);   // [5] DFS 실행

    // [6] 연결 요소 개수 출력
    int comp1 = countConnectedComponents(g.adj);
    cout << "[6] 연결 요소 수 (수동 그래프): " << comp1 << "\n";

    // [7] 경로 존재 여부 확인
    bool path1 = pathExists(g.adj, 0, 5);
    cout << "[7] 0과 5 사이 경로 존재? (수동 그래프): " << (path1 ? "Yes" : "No") << "\n";

    // [2~7] 파일 입력 방식 예제
    GraphList g2(0);
    g2.loadFromFile("graph_input.txt");

    BFS(g2.adj, 0);   // [4] BFS 실행 (파일 그래프)
    DFS(g2.adj, 0);   // [5] DFS 실행 (파일 그래프)

    int comp2 = countConnectedComponents(g2.adj);  // [6]
    cout << "[6] 연결 요소 수 (파일 그래프): " << comp2 << "\n";

    bool path2 = pathExists(g2.adj, 0, 5);          // [7]
    cout << "[7] 0과 5 사이 경로 존재? (파일 그래프): " << (path2 ? "Yes" : "No") << "\n";

    return 0;
}

 

// chap06_graph 전체 구현 + 입력 방식 2종류 (직접 addEdge vs 파일 입력)
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <limits>
#include <cstring>
#include <fstream>
#include <algorithm>
using namespace std;

const int INF = 1e9; // 무한대 값 정의

//--------------------------------------
// (생략된 부분 동일) 기존 코드 유지...

//--------------------------------------
// 8. 두 노드 간 경로 출력 (BFS 기반 경로 역추적)
// 실행 예: vector<int> path; if (findPath(g.adj, 0, 5, path)) ...
bool findPath(const vector<vector<int>>& adj, int u, int v, vector<int>& path) {
    int n = adj.size();
    vector<int> parent(n, -1);
    vector<bool> visited(n, false);
    queue<int> q;
    q.push(u);
    visited[u] = true;

    while (!q.empty()) {
        int cur = q.front(); q.pop();
        if (cur == v) break;
        for (int next : adj[cur]) {
            if (!visited[next]) {
                visited[next] = true;
                parent[next] = cur;
                q.push(next);
            }
        }
    }

    if (!visited[v]) return false; // 경로 없음

    for (int cur = v; cur != -1; cur = parent[cur])
        path.push_back(cur);
    reverse(path.begin(), path.end());
    return true;
}

//--------------------------------------
// 9. 싸이클 존재 여부 판별 (DFS 기반)
// 실행 예: bool has = hasCycle(g.adj);
bool dfsCycle(const vector<vector<int>>& adj, int v, int parent, vector<bool>& visited) {
    visited[v] = true;
    for (int next : adj[v]) {
        if (!visited[next]) {
            if (dfsCycle(adj, next, v, visited)) return true;
        } else if (next != parent) {
            return true; // back edge
        }
    }
    return false;
}

bool hasCycle(const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false);
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            if (dfsCycle(adj, i, -1, visited)) return true;
        }
    }
    return false;
}

//--------------------------------------
// main 함수 예시 실행
int main() {
    // [1] 인접행렬 예제 실행
    GraphMatrix mat(6);
    mat.addEdge(0, 1);
    mat.addEdge(0, 2);
    mat.addEdge(1, 2);
    mat.addEdge(1, 3);
    mat.addEdge(2, 4);
    mat.addEdge(4, 5);
    mat.printMatrix();

    // [2~5] 수동 방식으로 그래프 구성 후 BFS, DFS
    GraphList g(8);
    g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3);
    g.addEdge(2, 4); g.addEdge(3, 5); g.addEdge(4, 5);

    BFS(g.adj, 0);   // [4] BFS 실행
    DFS(g.adj, 0);   // [5] DFS 실행

    int comp1 = countConnectedComponents(g.adj);  // [6]
    cout << "[6] 연결 요소 수 (수동 그래프): " << comp1 << "\n";

    bool path1 = pathExists(g.adj, 0, 5);          // [7]
    cout << "[7] 0과 5 사이 경로 존재? (수동 그래프): " << (path1 ? "Yes" : "No") << "\n";

    // [8] 경로 출력
    vector<int> path;
    if (findPath(g.adj, 0, 5, path)) {
        cout << "[8] 경로 출력 (0 -> 5): ";
        for (int node : path) cout << node << " ";
        cout << "\n";
    } else {
        cout << "[8] 경로 없음\n";
    }

    // [9] 싸이클 유무 검사
    bool cycle1 = hasCycle(g.adj);
    cout << "[9] 싸이클 존재? (수동 그래프): " << (cycle1 ? "Yes" : "No") << "\n";

    // 파일 입력 그래프
    GraphList g2(0);
    g2.loadFromFile("graph_input.txt");

    BFS(g2.adj, 0);
    DFS(g2.adj, 0);

    int comp2 = countConnectedComponents(g2.adj);
    cout << "[6] 연결 요소 수 (파일 그래프): " << comp2 << "\n";

    bool path2 = pathExists(g2.adj, 0, 5);
    cout << "[7] 0과 5 사이 경로 존재? (파일 그래프): " << (path2 ? "Yes" : "No") << "\n";

    vector<int> path2vec;
    if (findPath(g2.adj, 0, 5, path2vec)) {
        cout << "[8] 경로 출력 (파일 그래프 0 -> 5): ";
        for (int node : path2vec) cout << node << " ";
        cout << "\n";
    }

    bool cycle2 = hasCycle(g2.adj);
    cout << "[9] 싸이클 존재? (파일 그래프): " << (cycle2 ? "Yes" : "No") << "\n";

    return 0;
}

 

전체코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <fstream>
using namespace std;

////////////////////////////////////////////////////////
// [1] 위상 정렬 함수 (BFS 방식) - 사이클 없을 때만 성공
////////////////////////////////////////////////////////
bool topologicalSort(const vector<vector<int>>& adjMatrix, vector<int>& result) {
    int N = adjMatrix.size();
    vector<int> indegree(N, 0);

    // 진입 차수 계산
    for (int j = 0; j < N; ++j)
        for (int i = 0; i < N; ++i)
            if (adjMatrix[i][j]) indegree[j]++;

    queue<int> q;
    // 진입 차수가 0인 정점을 큐에 삽입
    for (int i = 0; i < N; ++i)
        if (indegree[i] == 0) q.push(i);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        result.push_back(u);

        // u와 연결된 모든 v의 진입 차수를 줄임
        for (int v = 0; v < N; ++v) {
            if (adjMatrix[u][v]) {
                if (--indegree[v] == 0)
                    q.push(v);
            }
        }
    }

    return result.size() == N;  // 모든 정점을 방문했으면 성공
}

////////////////////////////////////////////////////////
// [2] 사이클 존재 여부 판단
////////////////////////////////////////////////////////
bool hasCycle(const vector<vector<int>>& adjMatrix) {
    vector<int> dummy;
    return !topologicalSort(adjMatrix, dummy); // 위상 정렬 실패 = 사이클 있음
}

////////////////////////////////////////////////////////
// [3] 가능한 모든 위상 정렬 출력 (DFS + 백트래킹)
////////////////////////////////////////////////////////
void allTopologicalSorts(vector<vector<int>>& adjMatrix, vector<int>& indegree,
                         vector<int>& path, vector<bool>& visited) {
    int N = adjMatrix.size();
    bool flag = false;

    for (int i = 0; i < N; ++i) {
        if (indegree[i] == 0 && !visited[i]) {
            // 정점 i를 선택하여 경로에 추가
            for (int j = 0; j < N; ++j)
                if (adjMatrix[i][j]) indegree[j]--;

            path.push_back(i);
            visited[i] = true;

            allTopologicalSorts(adjMatrix, indegree, path, visited);

            // 백트래킹
            visited[i] = false;
            path.pop_back();
            for (int j = 0; j < N; ++j)
                if (adjMatrix[i][j]) indegree[j]++;

            flag = true;
        }
    }

    // 모든 정점 사용한 경우 출력
    if (!flag && path.size() == N) {
        for (int x : path) cout << x << " ";
        cout << "\n";
    }
}

////////////////////////////////////////////////////////
// [4] 각 작업의 최소 완료 시간 계산
////////////////////////////////////////////////////////
vector<int> computeEarliestCompletion(const vector<vector<int>>& adjMatrix, const vector<int>& duration) {
    int N = adjMatrix.size();
    vector<int> indegree(N, 0);
    vector<int> completion(N, 0);

    // 진입 차수 계산
    for (int j = 0; j < N; ++j)
        for (int i = 0; i < N; ++i)
            if (adjMatrix[i][j]) indegree[j]++;

    queue<int> q;
    // 진입 차수가 0인 작업부터 시작 (초기 수행 가능 작업들)
    for (int i = 0; i < N; ++i) {
        if (indegree[i] == 0) {
            q.push(i);
            completion[i] = duration[i];
        }
    }

    while (!q.empty()) {
        int u = q.front(); q.pop();

        for (int v = 0; v < N; ++v) {
            if (adjMatrix[u][v]) {
                // 이전 작업 완료시간 + 현재 작업 수행시간 중 최대값
                completion[v] = max(completion[v], completion[u] + duration[v]);
                if (--indegree[v] == 0)
                    q.push(v);
            }
        }
    }

    return completion;
}

////////////////////////////////////////////////////////
// [5] 파일로부터 인접행렬 및 duration 벡터 읽기
////////////////////////////////////////////////////////
bool loadFromFile(const string& filename, vector<vector<int>>& adjMatrix, vector<int>& duration) {
    ifstream fin(filename);
    if (!fin) {
        cerr << "파일 열기 실패: " << filename << "\n";
        return false;
    }

    int N, M;
    fin >> N >> M;
    adjMatrix.assign(N, vector<int>(N, 0));

    // 간선 입력 받기
    for (int i = 0; i < M; ++i) {
        int u, v;
        fin >> u >> v;
        adjMatrix[u][v] = 1;
    }

    duration.resize(N);
    for (int i = 0; i < N; ++i)
        fin >> duration[i];

    return true;
}

////////////////////////////////////////////////////////
// [6] 메인 함수 - 실행
////////////////////////////////////////////////////////
int main() {
    vector<vector<int>> adjMatrix;
    vector<int> duration;

    // 🔷 파일로부터 그래프 및 duration 불러오기
    if (!loadFromFile("input.txt", adjMatrix, duration)) return 1;

    int N = adjMatrix.size();

    cout << "[1] 기본 위상 정렬 결과:\n";
    vector<int> result;
    if (topologicalSort(adjMatrix, result)) {
        for (int x : result) cout << x << " ";
        cout << "\n";
    } else {
        cout << "사이클이 존재하여 위상 정렬 불가\n";
    }

    cout << "\n[2] 사이클 존재 여부:\n";
    cout << (hasCycle(adjMatrix) ? "사이클 존재\n" : "사이클 없음\n");

    cout << "\n[3] 가능한 모든 위상 정렬:\n";
    vector<int> indegree(N, 0);
    for (int j = 0; j < N; ++j)
        for (int i = 0; i < N; ++i)
            if (adjMatrix[i][j]) indegree[j]++;
    vector<bool> visited(N, false);
    vector<int> path;
    allTopologicalSorts(adjMatrix, indegree, path, visited);

    cout << "\n[4] 각 작업의 최소 완료 시간:\n";
    vector<int> complete = computeEarliestCompletion(adjMatrix, duration);
    for (int i = 0; i < N; ++i)
        cout << "작업 " << i << ": 완료 시간 = " << complete[i] << "\n";

    return 0;
}