[Algorithm1] Kosaraju's algorithm(코사라주 알고리즘)

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

 

코사라주 알고리즘은 strongly connected component를 찾는 데 사용되는 그래프 알고리즘이다.

이 알고리즘은 그래프의 구조를 기반으로 각 vertex를 그룹화하고,

strongly connected component를 식별하는 데에 사용된다.

 

 

동작 과정

 

1. DFS를 수행해서 DFS forest

- 시작 정점은 임의로 선택함

- finish time 추적

2. 그래프의 모든 edge 반전

3. DFS를 다시 실행하여 다른 DFS forest를 만듬

- 이번에는 첫 번째 DFS 실행부터 finish time의 역순으로 vertex를 시작

4. SCCs는 두 번째 DFS forest의 다른 tree임

 

 

특징

 

* SCC 그래프는 Directed Acyclic Graph(비순환 그래프)이다.

비순환 그래프가 아니면, 두 개의 SCCs가 하나로 될 수도 있다.

 

* SCC의 finishing time은 SCC의 요소 중 가장 큰 finising time이다.

* SCC의 starting time은 SCC의 요소 중 가장 작은 starting time이다.

 

 

Runtime

 

finding SCCs takes O(n+m) time.