Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 방향 그래프의 약한 연결·강한 연결 여부 판별하기

DFS(깊이 우선 탐색)를 활용하면 주어진 방향 그래프가 약하게 연결(weakly connected)되어 있는지 강하게 연결(strongly connected)되어 있는지 판별할 수 있습니다. 이 글에서는 해당 문제를 해결하는 C++ 프로그램을 예제 코드와 함께 소개합니다.

핵심 개념: 약한 연결 vs 강한 연결

강하게 연결된 그래프란 그래프 내 임의의 두 정점 사이에 양방향 경로가 모두 존재하는 그래프를 의미합니다. 반면 약하게 연결된 그래프는 모든 간선의 방향을 무시하고 무방향 그래프로 간주했을 때에만 연결 그래프가 되는 경우를 말합니다.

이 프로그램은 코사라주(Kosaraju) 알고리즘을 기반으로 하며, 다음 단계로 동작합니다.

  1. 모든 정점에 대해 DFS를 수행하고, 탐색이 끝난 순서대로 정점을 스택에 저장합니다.
  2. 그래프의 모든 간선 방향을 뒤집은 전치 그래프(transpose graph)를 생성합니다.
  3. 스택에서 정점을 하나씩 꺼내며 전치 그래프에서 DFS를 수행합니다. 이때 각 DFS 트리가 하나의 강연결 요소(SCC)가 됩니다.
  4. 강연결 요소가 1개면 강하게 연결된 그래프, 2개 이상이면 약하게 연결된 그래프입니다.

사용되는 함수

Begin
    Function fillOrder() = 모든 정점을 스택에 채웁니다.
    a) 현재 노드를 방문 처리하고 출력합니다.
    b) 이 정점에 인접한 모든 정점에 대해 재귀 호출합니다.
    c) v에서 도달 가능한 모든 정점이 처리되면, v를 스택에 push 합니다.
End
Begin
    Function DFS() :
    a) 현재 노드를 방문 처리하고 출력합니다.
    b) 이 정점에 인접한 모든 정점에 대해 재귀 호출합니다.
End

예제 코드

#include <iostream>
#include <list>
#include <stack>
using namespace std;
class G {
    int m;
    list<int> *adj;
    // 함수 선언
    void fillOrder(int n, bool visited[], stack<int> &Stack);
    void DFS(int n, bool visited[]);
    public:
        G(int N); // 생성자
        void addEd(int v, int w);
        int print();
        G getTranspose();
};
G::G(int m) {
    this->m = m;
    adj = new list<int> [m];
}
void G::DFS(int n, bool visited[]) {
    visited[n] = true; // 현재 노드를 방문 처리하고 출력
    cout << n << " ";
    list<int>::iterator i;
    // 이 정점에 인접한 모든 정점에 대해 재귀 호출
    for (i = adj[n].begin(); i != adj[n].end(); ++i)
        if (!visited[*i])
            DFS(*i, visited);
}
G G::getTranspose() {
    G g(m);
    for (int n = 0; n < m; n++) {
        list<int>::iterator i;
        for (i = adj[n].begin(); i != adj[n].end(); ++i) {
            g.adj[*i].push_back(n);
        }
    }
    return g;
}
void G::addEd(int v, int w) {
    adj[v].push_back(w); // v의 리스트에 w 추가
}
void G::fillOrder(int v, bool visited[], stack<int> &Stack) {
    visited[v] = true; // 현재 노드를 방문 처리
    list<int>::iterator i;
    // 이 정점에 인접한 모든 정점에 대해 재귀 호출
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            fillOrder(*i, visited, Stack);
    Stack.push(v); // v에서 도달 가능한 모든 정점 처리 후 스택에 push
}
int G::print() { // 결과 출력 및 강연결 요소 개수 반환
    stack<int> Stack;
    bool *visited = new bool[m];
    for (int i = 0; i < m; i++)
        visited[i] = false;
    // 첫 번째 DFS로 완료 순서를 스택에 저장
    for (int i = 0; i < m; i++)
        if (visited[i] == false)
            fillOrder(i, visited, Stack);
    G graph = getTranspose(); // 역방향 그래프 생성
    for (int i = 0; i < m; i++) // 모든 정점을 미방문 상태로 초기화
        visited[i] = false;
    int count = 0;
    // 스택에 저장된 순서대로 정점을 처리
    while (Stack.empty() == false) {
        int v = Stack.top();
        Stack.pop(); // 스택에서 정점 pop
        if (visited[v] == false) {
            graph.DFS(v, visited);
            cout << endl;
            count++; // 새로운 강연결 요소를 찾을 때마다 카운트 증가
        }
    }
    return count;
}
int main() {
    G g(5);
    g.addEd(2, 1);
    g.addEd(3, 2);
    g.addEd(1, 0);
    g.addEd(0, 3);
    g.addEd(3, 1);
    cout << "주어진 그래프의 강연결 요소는 다음과 같습니다\n";
    if (g.print() > 1) {
        cout << "그래프는 약하게 연결되어 있습니다.";
    } else {
        cout << "그래프는 강하게 연결되어 있습니다.";
    }
    return 0;
}

실행 결과

주어진 그래프의 강연결 요소는 다음과 같습니다
4
0 1 2 3
그래프는 약하게 연결되어 있습니다.

코드 설명

예제 그래프는 정점 5개로 구성되어 있으며, 정점 0, 1, 2, 3은 서로 양방향으로 도달 가능한 하나의 강연결 요소를 이룹니다. 반면 정점 4는 어떤 간선과도 연결되어 있지 않아 자기 자신만으로 별도의 강연결 요소를 형성합니다.

따라서 강연결 요소의 개수는 총 2개이며, 프로그램은 print() 함수가 반환한 값이 1보다 크므로 이 그래프를 약하게 연결된 그래프로 판정합니다. 만약 그래프 전체가 하나의 강연결 요소로 구성되어 있다면 반환값이 1이 되어 강하게 연결된 그래프로 판정됩니다.

이 알고리즘은 DFS를 두 번 수행하므로 시간 복잡도는 정점 수를 V, 간선 수를 E라고 할 때 O(V + E)로 매우 효율적입니다.