강한 연결 요소(SCC) ; 타잔 알고리즘과 코사라주 알고리즘

 

▷ 개념

 

○ 강한 연결 방향그래프(Strongly Connected Digraph)

-> 어떤 두 정점을 잡든 간에 서로 연결이 되어 있는, 방향 경로가 존재하는 그래프.

 

 

 

○ 강한 연결 요소(Strongly Connected Component)

-> 어떤 두 정점을 잡든 서로 도달할 수 있는 경로가 있는 부분 방향 그래프. 같은 강한 연결 요소에 속하는 정점들은 서로 이동할 수 있는 방향 경로가 반드시 존재함. 사이클이 발생한다면 무조건 SCC에 해당하며 강한 연결 방향 그래프는 강한 연결 요소가 오직 하나. SCC를 하나의 정점으로 고려하여 각 SCC를 위상 정렬할 수 있음.

 

 

 

 

 

▷ 알고리즘

 

 

○ 타잔 알고리즘(Tarjan's Algorithm)

 

· 개념 : 모든 정점에 대해 DFS를 수행하여 SCC를 찾는 알고리즘. 코사라주 알고리즘에 비해 적용이 쉬움. 방향경로의 시작점으로 다시 돌아갈 수 있어야 같은 SCC에 속하는 것이라는 점을 이용함. 같은 SCC에 속하는 노드들은 같은 부모를 갖는다고 보고, 그 SCC에 속한 노드들 중에서 가장 id값이 작은 것을 부모로 지정함. id값은 DFS를 시작할 때 부여함.

 

 

· 알고리즘

 

1.  인접 정점에 방문하며 자기 자신을 스택에 넣고, DFS를 재귀적으로 수행. 

2. 인접 정점에 방문하였으니 아직 처리중인 상태일 경우  더 작은 값으로 부모값을 갱신.

3. 부모 노드의 DFS가 끝난 경우에는, 자신의 id값이 스택에서 나올 때까지 스택에 있는 노드들을 pop하고 scc 배열에 추가함.

4. 그렇게 만들어진 하나의 scc를 전체 SCC 배열에 추가함.

 

 

·프로그램

int id, nodeId[MAX];
bool finished[MAX];
vector<int> nodes[MAX];
vector<vector<int>> SCC;
stack<int> s;

int dfs(int x){
    nodeId[MAX] = ++id; //노드마다 고유한 아이디 부여
    s.push(x); //스택에 자기 자신을 삽입
    
    int parent = nodeId[x];
    
    for (int i=0; i<nodes[x].size(); i++) {
        int y = nodes[x][i];
        //방문 안 한 이웃
        if (nodeId[y] == 0) parent = min(parent, dfs(y));
        //처리 중인 이웃
        else if (!finished[y]) parent = min(parent,nodeId[y]);
    }
    
    if (parent==nodeId[x]) {
        vector<int> scc;
        while(1){
            int t = s.top();
            s.pop();
            scc.push_back(t);
            finished[t] = true;
            if (t==x) break;
        }
        SCC.push_back(scc);
    }
    return parent;
}

 

 

 

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

· 개념 : 주어진 방향 그래프의 역방향 그래프와 스택을 사용하여 SCC를 구하는 알고리즘. 방향 그래프와 역방향 그래프가 동일한 SCC를 구성한다는 것을 이용함.

 

 

· 알고리즘

 

1. 주어진 방향그래프의 역방향 그래프를 만들어 방향 그래프의 임의의 정점부터 DFS를 수행

2. DFS가 끝나는 순서대로 스택에 삽입함.

3. 아직 방문하지 않은 정점에 대해 다시 DFS를 수행

4. 모든 정점이 스택에 담긴 후에는 스택을 pop하여 나오는 정점부터 역방향 그래프에서 DFS를 수행함. 이미 방문한 정점은 pop만 시행

5. 이때 탐색되는 모든 정점을 SCC로 묶음

6. 스택이 빌 때까지 진행.

 

타잔 알고리즘에 비해 구현이 더 쉬운 편. 구체적인 구현은 생략.