Strongly Connected Component(SCC) 에 대한 깨달음 _ 알고리즘 타당성 증명

이번 글에서는 Strongly Connected Component를 찾는 알고리즘을 다루도록 하자.

이 강의는 고려대 전기전자공학과 김황남 교수님의 강의안 COMM208 Data Structure - Graph를 참고하였습니다.

 

먼저 SCC(Strongly Connected Component)의 정의를 알아보면

"SCC에 포함된 모든 vertex(node)에 대해서 임의의 두 vertex를 선택하면 그 사이의 path는 항상 존재한다."

는 성질을 만족하는 G(V,E)를 의미한다.

 

어떤 그래프가 주어지고 그 그래프 내에서 SCC를 찾는 알고리즘은 mDFS(modified Depth First Search)와 transpose 개념으로 구성되어 있다.

여기서 transpose란 digraph의 모든 edge 방향을 반대로 반전시키는 행위를 의미한다. ( a to b -> b to a )

아래는 슈도 코드이다.

전체 알고리즘은 세 단계로 나누어졌다고 할 수 있다.

1. Execute mDFS(G)

2. Generate transpose G^T

3. Execute mDFS(G) according to the descending order of f[] (여기서 f는 각 node의 finishing time)

 

예제를 들어보겠다.

먼저 mDFS를 통해서 각 노드의 finishing time을 측정한다.

예를 들어 a node의 finishing time : 16, e : 14, c : 12, g : 11 ...

그리고 전체 그래프를 transpose 시킨다.

마지막으로 transpose 시킨 graph에서 finishing time이 큰 node를 시작으로 mDFS를 다시 실행한다.

그러면 각 시작 node가 포함된 여러 개의 SCC가 찾아진다.

위 그림을 보았을 때 빨간색 a SCC -> 연두색 c SCC -> 파란색 g SCC -> 초록색 h SCC

순으로 SCC group을 찾을 수 있다.

 

여기서 이 알고리즘으로 했을 때 왜 SCC가 찾아지는지 생각해 보자.

 

알고리즘의 타당성 증명

1. Transpose 했을 때 SCC?

위 그림에서 보라색 부분은 SCC이다.

Transpose를 하더라도 SCC의 cycle 성질에는 아무런 영향을 주지 않아서 보라색 부분의 node cycle은 여전히 유효하다.

다시 3번을 보게 되면 mDFS를 했을 때 순환을 빠져나가지 않고 SCC를 잘 형성함을 알 수 있다.

 

2. 굳이 Transpose를 하는 이유?

Transpose를 하면 일단 SCC cycle 성질에는 아무런 영향을 주지 않는다는 건 오케이..

그런데 굳이 왜 하는가?

Transpose를 하지 않으면 제대로 된 SCC가 찾아지지 않아서 그렇다. 위 예제를 다시 한번 보자.

a, b, c node의 경우 finish time이 연속적인 친구들끼리 SCC를 형성한다고 볼 수 있다. 하지만...

d, h node의 경우 SCC가 아님에도 불구하고 서로 finish time이 연속적이다.

c, d node의 경우 SCC 임에도 서로 finish time이 연속적이지 않다.

이러한 문제의 이유는 Strongly Connected Component끼리의 bridge 가 있어서 그렇다.

{A,B,C} SCC -> {D,E,F} SCC edge 존재

먼저 알아야 할 사실이 있다.

위 상황처럼 {A, B, C} SCC -> {D, E, F} SCC 방향으로의 단 방향 edge가 있으면 {A,B,C} SCC 보다 {D,E,F} SCC가

더 빠르게 Search 된다는 점이다.

넘어가서

 

아래와 같이 SCC A, B, C, D가 있다고 했을 때 edge의 방향에 따라 Search 순서가 정해지게 된다.

그런데 Transpose를 하게 되면 그 순서가 반대가 된다.

이때 이전에 찾았던 finish time의 내림차순으로 mDFS를 시행하면 깔끔하게 각 SCC가 하나씩 찾아지게 된다.

(이전 순서와 Transpose 후 순서가 반대 -> 정확히 하나씩 SCC를 찾게 됨)

 

반론이나 질문은 환영입니다.