코사라주 알고리즘(시간복잡도, 구현 방법, 준비 사항)

코사라주 알고리즘 

강한 연결 요소(SCC)를 구하는 것이다

SCC란 사이클을 가지는 정점의 집합이다ㅣ

 

시간복잡도

코사라주 알고리즘은 dfs를 기반으로 한다 

인접리스트의 경우 O(V+E)로 가능하다

 

준비 사항

코사라주 알고리즘을 실행하기 위해서는

그래프

역방향 그래프

stack 

세가지가 필요하다

 

구현 방법

1. 역방향 그래프를 구한다

2. 원래 그래프에서 dfs를 실시한다

3. dfs가 끝나는 대로 stack에 정점을 넣을 수 있도록 한다.

4. stack에 끝에서 부터 역방향 그래프로 dfs를 실시한다

5. 종료 되거나 방문되지 않는 것들끼리 엮어져 있는것이 SCC가 된다

 

아래 글이 도움이 되었다

https://wondy1128.tistory.com/130

SCC-코사라주 알고리즘(Kosaraju's Algorithm)