Strongly Connected Component

0. 사전 지식

Undirected Graph

 

DFS Traversal makes Forest//

Undirected Graph는 시작점이 어디든 Tree 개수 일치

Directed Graph는 시작점 따라 Tree 개수가 다름.

 

1. 정의

 

Strongly Connected => 모든 쌍에서 길이 다 있음.

 

 

2. 특성

가질 수 있는 Edge 3종류

Cross, Back, Forward Edge

우->좌 Cross Edge는 가능하다. 좌->우는 DFS Traversal에 모순된다.

Leaf Node에서 좌-> 우 Cross Edge가 불가능 한 이유는

DFS Traversal알고리즘 상 더이상 인접 노드가 없을 때 까지 깊이 들어가는데

좌->우 Cross Edge 존재 시 우측 노드를 이미 추가했었어야 한다.

∴ DFS Traversal Algorithm에 모순.

 

3. 알고리즘

1. DFS Traversal 이용 Left, Right, Visit (Post Traversal 후위 순회법 적용)

2. PostNumber (종료 번호)를 종료시점에 따라 부여.

 

3. Kosaraju Algorithm

2번까지 해서 형성된 Tree를 거꾸로 뒤집음. (Post Number는 유지) => 뒤집어서 가장 큰 숫자부터 시작.

가장 큰 숫자 선택하는 방식으로 DFS 재순회.

 

 

 

PostNumber 낮은 수부터 시작 => Tree 최대한 쪼개져서(떨어져 나옴) Tree 개수 최대.

PostNumber 높은 수부터 시작 => Tree가 커져서 Tree 개수 최소.

(Topological Sort의 Queue의 담긴 순서와 같아진다.)// Main Idea!

 

 [Kosaraju Algorithm]

① (1차) DFS를 Post-Order로 수행

② 종료시점 Node 순서대로 PostNumber 기록 (Leaf Node일수록 숫자 낮아짐)

③ 1차 DFS 종료이후 Edge 연결 순서를 뒤집음.

④ MAX(PostNumber)를 선택하면서 DFS

⑤ Edge 연결이 뒤집혔으므로 역방향 그래프에서부터 DFS를 수행한다

이때② 로부터 PostNumber 큰 순서대로 방문하며 Strongly Connected Component Tree가 최대 개수로 형성된다.

 

4. Time Complexity

DFS를 총 1회 => Edge 뒤집기 => DFS max(postNumber) 

 

n + 2m + n(PostNumber 매기기) // + n + 2m

3n + 4m -> O( n + m ) 

∴ O (n+m)