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

강한 연결 요소( Strongly Connected Component, SCC )

강한 연결 요소는 방향 그래프에서 모든 정점에 도달하는 경로가 존재하는 최대 부분 집합을 말합니다.

다른 말로 하면, 강한 연결 요소는 순환 경로가 있는 부분 집합을 뜻합니다.

 

아래의 이미지를 보면

 

강한 연결 요소( SCC )

 

1과, 2번, 3번 정점 중, 어떤 두 정점을 선택해도, 한 정점에서 다른 정점으로 도달할 수 있는 경로가 존재합니다.

반면, 3번에서 출발하여 4번 정점엔 도달할 수 있지만, 4번 정점에서 3번 정점으로는 이동할 수 없습니다.

따라서, { 1, 2, 3 } 집합이 가장 크면서 서로 경로가 존재하는 부분 집합입니다.

이 부분 집합을 강한 연결 요소( strongly connected component )라고 합니다.

이 그래프에서는 강한 연결 요소가 하나만 있는 것이 아닙니다.

{ 4, 5 }도 강한 연결 요소이고,

하나의 정점으로 이루어진 { 6 } 집합도 강한 연결 요소에 해당합니다.

 

강한 연결 요소는 방향이 존재하는 그래프가 주어졌을 때, 의미가 있습니다.

방향이 없는 그래프의 임의의 두 정점 사이엔 항상 경로가 존재하고, 그래서 그래프 전체가 하나의 강한 연결 요소가 되기 때문입니다.

 

타잔( Tarjan ) 알고리즘

타잔 알고리즘은 주어진 방향 그래프에서 강한 연결 요소( SCC )를 찾아내는 알고리즘입니다.

 

이 알고리즘은 깊이 우선 탐색( Depth First Search, DFS ) 방법으로 정점을 탐색하면서, 강한 연결 요소를 찾는 알고리즘입니다.

강한 연결 요소는 순환 경로가 있는, 그래프의 부분 집합입니다.

따라서, 순환 경로를 찾는 방법이라고 할 수도 있습니다.

 

아주 간단한 예를 들어보겠습니다.

 

예제1

 

위와 같은 그래프에서 탐색을 10번 정점부터 시작하겠습니다.

이렇게 하는 이유는, 설명 과정에서 의도치 않게 정점의 이름과 탐색하는 순서를 혼동할 수 있기 때문입니다.

중요한 것은 탐색하는 순서입니다.

 

 

10번 정점을 탐색했다는 의미로 버퍼에 루프 번호 1을 저장합니다. visited [10] = 1.

이 루프 번호는 정점의 번호와 상관없이, 탐색된 순서를 기록하기 위한 번호입니다.

그리고, 루프 번호를 증가시킵니다.

또, 10번 정점을 스택( stack )에 넣습니다.

 

 

10번과 연결된 5번 정점을 탐색합니다.

루프 번호 2를 부여합니다. visited [5] = 2.

순환 경로를 찾을 때까지, 정점을 탐색할 때마다 루프 번호를 부여하고, 다시 루프 번호를 증가시킵니다.

또, 5번 정점을 스택( stack )에 넣습니다.

 

5번 정점과 연결된 1번 정점을 탐색합니다. visited [1] = 3.

1번 정점을 스택( stack )에 넣습니다.

 

만약, 어떤 정점에서 순환 경로를 찾았다면 그 정점이 부여받은 루프 번호 보다, 이전에 탐색했던 순환 경로에 있는 정점의 루프 번호 L이 더 작을 것입니다.

 

 

1번 정점은 10번 정점과 연결되어 있으므로, 순환 경로가 있습니다.

탐색 순서대로 부여받은 루프 번호 visited [1] = 3보다, 당연히 visited [10] = 1이 더 작습니다.

이 작은 루프 번호 L( =1)을 탐색 종료 시 반환합니다.

 

 

그리고, 이전에 탐색한 정점 5번으로 돌아가서, 이 정점이 가진 번호와 루프 번호 L을 비교합니다.

루프 번호 L이 더 작다면, 이 정점 5번보다 이전에 루프를 시작한 정점이 있다는 얘깁니다.

그래서, 다시 더 작은 번호 L을 탐색 종료 시 반환합니다.

이 과정을 정점이 가진 루프 번호와 L이 같을 때까지 수행합니다.

 

 

이제, 정점 10은 루프 번호 visited [10] = 1과 L = 1의 값이 같습니다.

그럼, 지금까지 스택에 저장되어 있는 정점들이 순환 경로를 가지고 있는 부분 집합이 됩니다.

이렇게 하나의 SCC를 구했습니다.

 

 

이 과정을 코드로 작성하면 다음과 같습니다.

#define SIZE    10  // 정점의 개수

vector<int> graph[SIZE+1];	// 그래프
int visited[SIZE+1];

int DFS( int vert, int& idx, stack<int>& st){

    visited[vert] = idx++;	// 루프 번호 부여
    st.push(vert);	// 스택에 정점 저장

    int L = visited[vert];
    
    for( int x : graph[vert]){
        if ( !visited[x] ){
            L = min( L, DFS( x, idx, st));	// 다음 연결된 정점 탐색
        }
        else{	// 순환 경로 발견
            L = min( L, visited[x]);
        }
    }

    if ( L == visited[vert]){	// SCC 구성
    	// Do something for scc
    }
    
    return L;	// 연결된 경로의 더 작은 루프 번호 반환
}

// main ---------------------------------------------
DFS(10, 1);	// call Tarjan Algorithm

위의 함수가 타잔 알고리즘의 주요 골격입니다.

이 골격을 가지고, 좀 더 확장된 예제를 보겠습니다.

 

확장된 예제

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

1번을 스택에 넣습니다.

 

2번 정점을 탐색합니다.

2번을 스택에 넣습니다.

 

3번 정점을 탐색합니다.

3번을 스택에 넣습니다.

설명을 위해서, 3번 정점에서 4번 정점과 먼저 연결되어 있다고 가정합니다.

 

 

4번 정점을 탐색하고 visited [4] = 4 루프 번호를 부여합니다.

그리고 4번을 스택에 넣습니다.

그런데, 4번 정점에서 연결된 간선이 없으므로, 부여된 루프 번호가 L과 같습니다.

{ 4 } SCC를 찾았습니다.

스택에서 4번 정점을 제거합니다.

 

다시 3번 정점으로 돌아와, 이번에 5번 정점과 먼저 연결되어 있다고 가정합니다.

 

5번 정점을 탐색하고 visited [5] = 5 루프 번호를 부여합니다.

5번을 스택에 넣습니다.

그리고, 3번 정점과 연결되어 있으므로 순환 경로가 존재합니다.

더 작은 루프 번호 L = visited [3]을 반환합니다.

 

 

다시 3번 정점으로 돌아와, 3번 정점에 연결된 마지막 1번 정점을 탐색합니다.

그런데, 1번 정점과 연결되어서 순환 경로가 다시 존재합니다.

따라서, L을 visited [1]로 설정하고 반환합니다.

 

 

역순으로 2번 정점을 지나, 1번 정점에서 루프 번호와 L이 같게 되었습니다.

{ 1, 2, 3, 5 } SCC가 구해졌습니다. 

 

 

이제, 마지막 정점인 6을 탐색합니다.

그런데, 6번 정점은 다른 정점과 순환 경로를 만들 수 없습니다.

단방향 간선만 있기 때문입니다.

그런데, 정점 3번과의 사이에 간선이 있으므로 불필요한 탐색이 발생합니다.

이러한 경우를 막기 위해서, 이미 SCC를 이루는 정점들에 표시를 합니다.

여기서는 finished [SIZE+1] 변수를 사용했습니다.

{ 1, 2, 3, 5 }는 이미 SCC를 구성했으므로, finish [3] = true로 표시하여, 3번 정점을 탐색하지 않도록 위의 코드를 변경합니다.

 

모든 SCC를 구분해 놓은 모습

 

이렇게 해서 완성된 코드는 다음과 같습니다.

#define SIZE    10  // 정점의 개수

vector<int> graph[SIZE+1];	// 그래프
int visited[SIZE+1];
bool finished[SIZE+1];	// scc를 이룬 정점 표시

int DFS( int vert, int& idx, stack<int>& st){

    visited[vert] = idx++;	// 루프 번호 부여
    st.push(vert);	// 스택에 정점 저장

    int L = visited[vert];
    
    for( int x : graph[vert]){
        if ( !visited[x] ){
            L = min( L, DFS( x, idx, st));	// 다음 연결된 정점 탐색
        }
        else if ( !finished[x] ){	// scc를 구성하지 않은 정점만 대상으로 탐색
            L = min( L, visited[x]);	// 순환 경로 발견
        }
    }

    if ( L == visited[vert]){	// SCC 구성
    	
        vector<int> scc;	// scc를 이루는 정점을 저장
        while ( !st.empty()){
            int x = st.top();	// 스택을 비우면서 scc 구성
            st.pop();

            scc.push_back(x);
            finished[x] = true;	// 이미 scc를 구성하는 정점 표시
            
            if ( x == vert) // scc를 구성하는 첫 번째 정점까지 순환
                break;
        }

        // Do something for scc
    }
    
    return L;	// 연결된 경로의 작은 루프 번호 반환
}

// main ---------------------------------------------
int main(){

    int V = 6; // 정점 개수       
    
    // 그래프 구성
    graph[1].push_back(2);
    graph[2].push_back(3);
    graph[3].push_back(4);
    graph[3].push_back(5);
    graph[3].push_back(1);
    graph[5].push_back(3);
    graph[6].push_back(3);

    stack<int> st;
    int idx = 1;
    
    for( int i = 1; i <= V; i++){

        if ( finished[i]) // 이미 scc를 이루는 정점 제외
            continue;
        
        DFS( i, idx, st);
    }
    
    return 0;
}