[Algorithm] 강한 결합 요소(Strongly Connected Component)

max9106·2020년 2월 7일
0

강한 결합 요소란?

SCC라고도 부르며, 그래프 안에서 강하게 결합된 정점 집합을 뜻한다.

같은 SCC에 속하는 두 정점은 서로 도달이 가능하다.

싸이클이 발생하는 경우 SCC이다. 즉, 방향 그래프일 때만 의미가 있다. 무향 그래프인 경우 그래프 전체가 SCC이기 때문에 의미가 없다.

SCC를 추출하는 알고리즘은 2가지가 있다.

  1. 코사라주 알고리즘: 구현이 쉬움
  2. 타잔 알고리즘: 적용이 쉬움

타잔 알고리즘

모든 정점에 대해서 DFS를 수행해서 SCC를 찾는다.

부모에서 출발하여, 자식을 거친 후 다시 부모로 돌아올 수 있는 경로가 있어야 SCC가 성립된다.

부모에서 자식으로 나아가는 알고리즘으로 DFS 알고리즘이 적용된다.

  1. 부모 값을 자기자신으로 표시하고, 시작점을 스택에 넣는다.

  2. 자식(인접노드)으로 나아가, 부모 값을 자기자신으로 표기한 후 스택에 넣는다.

  3. 2번을 반복하다가, DFS가 끝나지 않았는데, 스택에 있는 값이 인접노드인 경우, 자신의 부모값을 해당 인접노드의 값으로 바꿔준다.

  4. 거꾸로 가면서 부모값을 갱신하고, 스택에서 자기자신의 값을 꺼낼 때 까지 진행한다. 자기 자신 값을 만나면 그때까지 뽑아진 것들의 집합이 하나의 SCC집합이다.

구현

시간복잡도: O(V+E)

#include <iostream>
#include <vector>
#include <stack>
#define MAX 10001 // 가능한 총 노드 수

using namespace std;

int id; // 각 노드마다 고유한 번호를 할당하기 위함
int d[MAX]; // 각 노드의 방문 여부 

bool finished[MAX]; // 특정 노드의 DFS가 끝났는지 확인 
vector <int> a[MAX]; // 실질적으로 노드를 담는 배열
vector <vector <int> > SCC; // 한 그래프에서 여러개가 나올 수 있기 때문에 2차원 벡터 

stack<int> s;

// DFS는 총 정점의 갯수만큼 실행
int dfs(int x) {
    d[x] = ++id; // 노드마다 고유한 번호 할당(맨 처음에 부모로 설정되는 값)
    s.push(x); // 스택에 자기자신 삽입

    int parent = d[x]; // 자신의 부모 값

    // 인접한 노드를 하나씩 확인
    for(int i=0;i<a[x].size();i++) {
        int y = a[x][i]; // 인접한 노드 가리킴 

        // 방문한 적이 없다면
        if(d[y]==0) {
            parent = min(parent, dfs(y));  // 해당 노드로 dfs하여 더 작은 값으로 부모
        } else if(!finished[y]) { // 방문은 했지만, 아직 처리가 안된 노드(현재 DFS를 수행하고 있는 노드)
            parent = min(parent, d[y]); // 처리되고 있는 값의 부모와 비교 
        }
    }

    // 부모 노드가 자기자신인 경우 
    if(parent==d[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; // 자신의 부모 값 반환
}

int main(void) {
    int v = 11; // 노드 수

    a[1].push_back(2);
    a[2].push_back(3);
    a[3].push_back(1);
    a[4].push_back(2);
    a[4].push_back(5);
    a[5].push_back(7);
    a[6].push_back(5);
    a[7].push_back(6);
    a[8].push_back(5);
    a[8].push_back(9);
    a[9].push_back(10);
    a[10].push_back(11);
    a[11].push_back(3);
    a[11].push_back(8);

    for(int i=1;i<=v;i++) {
        if(d[i]==0) dfs(i);
    }

    printf("SCC의 갯수: %lu\n", SCC.size());

    for(int i=0;i<SCC.size();i++) {
        printf("%d번째 SCC: ", i+1);

        for(int j=0;j<SCC[i].size();j++) {
            printf("%d ", SCC[i][j]);
        }

        printf("\n");
    }

    return 0;
}

위상정렬과 함께 사용하는 알고리즘이다. 각 SCC그룹을 정점으로 삼아서 전체그룹을 구성했을 때, 싸이클이 발생하지 않는 방향그래프가 된다.

reference: https://www.youtube.com/watch?v=H_Cg3-rv7RU&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=28

profile
이전 블로그: https://blog.naver.com/max9106

0개의 댓글