[C++] 코사라주( Kosaraju ) 알고리즘 ( Strongly Connected Component, SCC 구하기 )

코사라주( Kosaraju ) 알고리즘

코사라주 알고리즘은 방향 그래프에서 강한 연결 요소( SCC )를 구하는 알고리즘입니다.

여기서, 강한 연결 요소는 주어진 방향 그래프에서 임의의 두 정점을 선택했을 때, 그 두 정점 간에 경로가 존재하는 최대 부분 집합입니다.

 

이와 같은 알고리즘으로는 타잔( Tarjan ) 알고리즘이 있습니다.

강한 연결 요소와 타잔 알고리즘은 자세한 내용은 여기에서 볼 수 있습니다.

[C++] 타잔( Tarjan ) 알고리즘 ( Strongly Connected Component, SCC 구하기 )

 

코사라주 알고리즘도 타잔 알고리즘과 마찬가지로 깊이 우선 탐색( Depth First Search, DFS ) 방식으로 정점을 탐색합니다.

그렇지만, 타잔 알고리즘과 달리, 깊이 우선 탐색을 두 번 수행하는 특징이 있습니다.

 

코사라주 알고리즘은 첫 번째 탐색 시, 탐색 과정을 스택에 저장합니다.

이때, 이 탐색 과정 순서를 그대로 반복하기 위해서 가장 깊숙이 탐색할 수 있는 정점까지 내려갔다가 올라오면서 스택에 정점을 저장합니다.

이 과정에서 indegree가 0인 정점이 있다면, stack의 가장 꼭대기에 위치하게 됩니다.

참고로, indegree는 정점으로 들어오는 간선의 개수를 말합니다.

 

그리고, 현재 그래프의 방향을 반대로 뒤집습니다.

마지막으로, 스택에 저장된 탐색 순서대로 역방향의 그래프를 깊이 우선 탐색하면서 SCC를 구합니다.

 

이 알고리즘이 작동하는 이유는 강한 연결 요소인 그래프의 부분 집합은 역방향으로 탐색하더라도, 순환 경로가 반드시 존재할 것이기 때문입니다.

 

아래 이미지의 예제를 통해서, 어떻게 SCC를 구하는지를 좀 더 구체적으로 따라가 보겠습니다.

이 예제는 위의 타잔 알고리즘 설명을 할 때의 예제와 같습니다.

 

 

임의로 1번 정점부터 탐색을 시작합니다.

그리고, 깊이 탐색으로 4번 정점까지 먼저 탐색하고, 스택에 4를 넣습니다.

 

 

그다음, 5번 정점을 탐색하고, 스택에 5를 넣습니다.

 

 

그다음, 3번, 2번, 1번 순으로 탐색을 거슬러 올라오면서 스택에 넣습니다.

 

6번 정점은 일방 방향뿐이므로, 다음 DFS 시에 탐색됩니다.

 

이제, 위의 그래프의 방향을 반대로 변경합니다.

그리고, 스택에 저장된 정점 순으로 깊이 우선 탐색을 합니다.

 

역방향 그래프

 

먼저, 6번 정점은 다른 정점과 연결이 없으므로 정점 한 개를 가진 SCC를 만듭니다.

 

그, 다음 1번 -> 3번 -> 2번 -> 5번 순으로 DFS를 하면서 정점을 모아 SCC를 만듭니다.

 

 

마지막으로, 4번 정점이 혼자서 SCC를 만듭니다.

 

 

이렇게 해서, 스택이 비워지면 탐색이 끝납니다.

 

이러한 과정을 코딩으로 변경하면 아래와 같습니다.

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

#define SIZE    10

vector<int> graph[SIZE];
vector<int> rgraph[SIZE];   // reversed graph

vector< vector<int> > scc_arr;  // scc 버퍼
bool visited[SIZE];

void DFS1( int vert, stack<int>& st){

    visited[vert] = true;
    
    for( int x : graph[vert]){	// 주어진 그래프
        
        if ( !visited[x] ){
            DFS1( x, st);
        }
    }

    st.push(vert);
}

void DFS2( int vert, vector<int>& scc){

    visited[vert] = true;
    scc.push_back(vert);	// 탐색 시 거치는 정점들이 scc의 원소가 됩니다.

    for( int x : rgraph[vert]){	// 방향을 거꾸로 한 그래프
        
        if ( !visited[x] ){
            DFS2( x, scc);
        }
    }
}

int main(){

    int V = 6;

    graph[1].push_back(2);
    graph[2].push_back(3);
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[3].push_back(5);
    graph[5].push_back(3);
    graph[6].push_back(3);

    // reverted graph
    rgraph[2].push_back(1);
    rgraph[3].push_back(2);
    rgraph[1].push_back(3);
    rgraph[4].push_back(3);
    rgraph[5].push_back(3);
    rgraph[3].push_back(5);
    rgraph[3].push_back(6);

    stack<int> st;

    for( int i = 1; i <= V; i++){

        if ( !visited[i]){
            DFS1(i, st);    // 원래 그래프 탐색
        }
    }

    fill( visited, visited+SIZE, false);    // visited 배열 초기화

    while( !st.empty()){
        int vert = st.top();    // 스택에 저장된 순서대로 탐색
        st.pop();

        if ( !visited[vert]){
            
            vector<int> scc;
            
            DFS2( vert, scc);   // 역방향 그래프 탐색

            sort( scc.begin(), scc.end());
            scc_arr.push_back( move(scc));  // 구한 scc 저장
        }
    }

    int scc_cnt = scc_arr.size();	// scc의 개수
    sort( scc_arr.begin(), scc_arr.end());	// 보기 좋게 정렬

    // print result
    cout << scc_cnt << endl;

    for( int i = 0; i < scc_cnt; i++){
        for( int x : scc_arr[i]){
            cout << x << " ";
        }
        cout << -1 << endl;
    }

    return 0;
}