Strong Connected Component - Gabow 알고리즘

Strong Connected Components(이하 SCC)를 구하기 위한 몇가지 알고리즘이 있는데, 그중에서 Gabow의 알고리즘은 간단하게 살펴보겠습니다.

 

SCC를 구하는 알고리즘은 Gabow이외에도 여러가지가 있는데, 대표적으로 Kosaraju 알고리즘과 Tarjan 알고리즘이 있습니다.

 

Kosaraju 알고리즘과 Tarjan 알고리즘이 궁금하다면 각각 다음 블로그를 참조하는 것을 추천드립니다.

 

https://wondy1128.tistory.com/130

SCC-코사라주 알고리즘(Kosaraju's Algorithm)

 

https://m.blog.naver.com/kks227/220802519976

강한 연결 요소(Strongly Connected Component) (수정: 2019-08-03)

 

우선 먼저 코드를 살펴보겠습니다.

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;
const int MAX = 10000;
 
int V, E, cnt, pre; // V = vertex, E = Edge, cnt = # of SCC, pre = predreder of vertex
vector<int> adj[MAX]; // graph
bool marked[MAX]; // marked[v] = vertex V is visited
bool finished[MAX]; // finished[v] = vertex V is finished
int preoreder[MAX]; // predorder of v
stack<int> S1; 
stack<int> S2;
vector<vector<int>> SCC;
 
void DFS(int curr){
    marked[curr] = true;
    preoreder[curr] = pre ++;
    S1.push(curr);
    S2.push(curr);
    for(int next: adj[curr]){
        if(!marked[next]) DFS(next);
        else if(!finished[next]){
            while(preoreder[S2.top()]>preoreder[next]) {
                S2.pop();
            }
        }
    }
    
    // found strong component containing v
    if(S2.top() == curr) {
        S2.pop();
        vector<int> currSCC;
        int w;
        do {
            w = S1.top();
            S1.pop();
            currSCC.push_back(w);
            finished[w] = true;
        }  while(w != curr);
        SCC.push_back(currSCC);
        cnt ++;
    }
}

 

위의 Tarjan 알고리즘을 읽어보셨다면, 매우 비슷한 형태임을 눈치채셨을겁니다. 다만 접근방식이 다소 상이합니다. 우선 처음에 stack을 2개 선언합니다. 하나의 스택에는 preoreder에 따라 저장을 합니다. 그리고 다른 스택에는 SCC set에서 가장 preorder가 낮은 노드만을 저장하게 됩니다. 그리고 현재 탐색하는 vertex가 후자의 스택의 top과 같아지면 reorder순으로 쌓은 스택에서 하나씩 pop을 하게되면 현재와 같은 vertex가 나오게 되고 pop이 된 vertex들과 SCC의 하나의 set이 됩니다.

 

성능은 다음과 같다고 합니다. node(vertex)수와 edge가 많아질수록 Gabow 알고리즘이 Tarjan 알고리즘보다 비교적 좋은 성능을 나타낸다는 결과를 보여주는 논문은 있는데, 수치적으로 해석하기보다는 실험적으로 얻은 결과라 참고만 하는 것이 좋을 것 같습니다.

 

Analysis of Strongly Connected Components (SCC) Using Dynamic Graph Representation