[Algorithms] 3.4 Strongly connected components

해당 글은 Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani를 정리한 스터디 노트입니다.해석하면서 정리한 글입니다.

3.4 Strongly connected components

3.4.1 Defining connectivity for directed graphs

undirected graphs의 연결은 매우 간단합니다. 연결되지 않은 그래프는 natural and obvious 방식으로 여러 개의 연결된 구성요소로 분해될 수 있습니다.

undirected graph의 경우, 각각의 connected components에 대해 DFS를 실행시키면 됩니다.
directed graph의 경우, connectivity를 다음과 같이 정의합니다.
- 두 노드 u,v가 서로 connected 라는 것은, u에서 v로 가는 path가 존재하며, v에서 u로 가는 path도 존재한다는 것으로 해석할 수 있습니다.
이 연결 관계를 통해, strongly connected components 를 정의할 수 있습니다.
- 즉, 이 관계는 directed graph를 V로 분할(parititions)하는 disjoint sets입니다.

각각의 strongly connected component를 하나의 메타노드로 표현해 메타그래프로 만들 수 있습니다.
이렇게 만들어진 메타그래프는, dag 형태가 됩니다. pf) 만약에 여러 개의 strongly connected components가 하나의 cycle을 포함한다면, 하나의 strongly connected components로 합쳐지게 됩니다.

Property 모든 directed graph는 해당 그래프의 strongly connected components로 이루어진 하나의 dag입니다.
즉, directed graph는 2가지의 연결성 구조를 갖고 있는데, 상위레벨에 dag로 간단하게 표현할 수 있거나(선형으로 표현 가능), 하위레벨에 각 dag 속 세부 그래프로 표현할 수 있습니다.

3.4.2 An efficient algorithm

directed graph를 strongly connected components로 분해하는 것은 굉장히 유용합니다. 분해 과정은 linear time 으로 찾을 수 있습니다.(DFS+α)

Property 1 만약 explore 서브루틴이 노드 u에서 시작하면, 그 서브루틴은 u로부터 도달가능한 모든 노드들을 방문했을 때 정확히 종료됩니다.

즉, (메타 레벨에서) sink strongly connected component인 노드에 대해 탐색 서브루틴을 호출하는 경우, 정확히 해당 component를 검색합니다. (= 메타레벨에서 종료한다는 뜻, 해당 component에서만 검색한다는 뜻)
이를 통해 하나의 strongly connected component를 찾는 방법을 알 수 있지만, 여전히 2가지 문제 존재합니다.
- (A) 확실히 sink strongly connected component에 놓여져 있는 노드를 어떻게 찾을까?
- (B) sink component를 찾았다면, 이후에 어떻게 반복해야할까? (A)를 확실히 찾을 수는 없지만, 반대로 source strongly connected component를 찾는 방법은 존재합니다. (↓)

Property 2 DFS를 통해 가장 높은 post숫자를 가진 노드는 source strongly connected component에 반드시 놓여져 있습니다.

이를 일반적으로 나타내면 아래와 같습니다. (↓)

Property 3 만약 strongly connected components $C$와 $C’$에 대해서 $C$ 안에 있는 노드로 가는 엣지가 존재할 때, $C$에서 가장 큰 post number는 $C’$에서 가장 큰 post number 보다 큽니다.

pf) 2가지 경우를 생각할 수 있습니다.

case 1)
- DFS가 $C’$이전에 $C$를 탐색한다면, property 1에 의해서 $C$과 $C’$ 모두 끊기지 않고 탐색한 것 입니다.
- 따라서 $C$에 첫번째로 방문한 노드가 어떤 $C’$의 노드보다도 늦게 끝나므로 post number가 클 수밖에 없습니다.
case 2)
- DFS에 의해 $C′$이 먼저 탐색된 경우, property 1에 의해서 $C$의 노드들을 보기도 전에 종료됩니다.

그럼 property를 다르게 해석해보겠습니다.

property 3를 “strongly connected components는 그들 내부의 가장 높은 post numbers의 내림차순으로 정렬해서 linearized 할 수 있다”라는 뜻으로 볼 수 있습니다.
property 2는 그래프 G의 source strongly connected components 안에 있는 노드 하나를 찾을 수 있게 해줍니다.

하지만 저희가 찾고 싶었던 노드는 source가 아니라 sink였습니다. 이를 어떻게 해결할 수 있을까요? (A)

$G^R$라는 reverse그래프를 생각해보겠습니다.
$G^R$과 $G$는 같은 strongly connected components를 갖고 있습니다.
따라서, $G^R$에 대해 DFS를 돌려서 나오는 $G^R$의 source components로부터 가장 높은 post 숫자를 가진 노드가 나오게 될 것 입니다.
결국 $G$의 관점에서 sink components로 볼 수 있습니다.
(A)를 $G^R$의 source를 찾는 것으로 해결할 수 있습니다!

그렇다면, first sink component를 찾은 이후 어떻게 반복해야할까요? (B)

Property 3을 이용해보겠습니다.
첫번째 strongly connected component를 찾고 나서 그래프로부터 그 component를 지우고 나면, 나머지 노드들 중에서 가장 높은 post 숫자를 가진 노드는 다시 sink component에 속하게 됩니다.
따라서 $G^R$에 대해 DFS를 처음 수행할 때, post 숫자를 매기는 것을 기억시켜놨다가 순서대로 strongly connected components를 출력하면 됩니다.

이를 알고리즘으로 정리하면 다음과 같습니다.

$G^R$에 대해 DFS 수행합니다.
$G$에 대해 undirected connected components 알고리즘(Section 3.2.3)을 수행하고, DfS 중 step1부터 vertex를 post number의 내림차순으로 처리합니다.

이 알고리즘은 linear-time 입니다. 구체적으로 linear-time에 있는 상수만 기존 straight depth-first search의 2배입니다.

위 그래프를 한 번 살펴보겠습니다.

step 1) $G^R$의 DFS를 탐색합니다.
- <G, I, J, L, K, H, D, C, F, B, E, A> 로 나열됩니다.
step 2) $G^R$의 DFS 결과로 나온 post 숫자 내림차순으로 recursive하게 components를 체크합니다.
- {G, H, I, J, K, L}, {D}, {C, F }, {B, E}, {A} 를 찾습니다.
  - $G$ ($G^R$ 제일 높은 숫자) 를 기준으로 $G$에 대해 DFS 돌리고 제거한 뒤 다시 $D$($G^R$ 나머지에서 제일 높은 숫자)를 기준으로 $G$에 대해 DFS 돌리면서 반복해줍니다.

Reference

Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani(http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf)