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

C++로 그래프의 강결합 요소(Strongly Connected Components) 찾기

개요

주어진 방향 그래프(directed graph)가 약하게 연결(weakly connected)된 그래프인지, 아니면 강하게 연결(strongly connected)된 그래프인지는 깊이 우선 탐색(DFS)을 활용하여 판별할 수 있습니다. 이 글에서는 그 대표적인 방법인 코사라주(Kosaraju) 알고리즘을 이용해 그래프의 강결합 요소(Strongly Connected Component, SCC)를 찾는 C++ 프로그램을 소개합니다.

강결합 요소란 그래프 내 임의의 두 정점 u, v에 대해 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는 정점들의 최대 부분집합을 의미합니다.

핵심 함수의 동작 원리

fillOrder() — 스택 채우기

  1. 현재 노드를 방문 처리합니다.
  2. 이 정점에 인접한 모든 정점에 대해 재귀적으로 탐색을 진행합니다.
  3. v에서 도달 가능한 모든 정점의 처리가 끝나면 v를 스택에 push합니다.

DFS() — 깊이 우선 탐색

  1. 현재 노드를 방문 처리하고 출력합니다.
  2. 이 정점에 인접한 모든 정점에 대해 재귀 호출을 수행합니다.

C++ 구현 예제

#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에서 도달 가능한 모든 정점 처리 후 v를 스택에 저장
}

int G::print() {                 // 결과 출력
    stack<int> Stack;
    bool *visited = new bool[m];
    for (int i = 0; i < m; i++)
        visited[i] = false;

    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();             // 스택에서 정점을 꺼냄
        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
그래프는 약하게 연결되어 있습니다.

결과 해석

정점 4는 어떤 간선으로도 연결되어 있지 않아 스스로 하나의 강결합 요소를 이루고, 정점 0, 1, 2, 3은 서로 도달 가능하므로 하나의 강결합 요소로 묶입니다. 즉, 강결합 요소가 두 개 이상 존재하므로 이 그래프는 강하게 연결된 그래프가 아니며, 프로그램은 이를 약하게 연결된 그래프로 판정합니다.

시간 복잡도

코사라주 알고리즘은 DFS를 두 번 수행하고 그래프를 한 번 전치하므로, 정점 V개와 간선 E개를 기준으로 O(V + E)의 시간 복잡도를 가집니다. 공간 복잡도 또한 O(V + E)입니다.