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

방향 그래프(Directed Graph) 에서 SCC (Strongly Connected Component) 를 코사라주 알고리즘을 이용해 구하는 방법이다. 

① 주어지는 방향 그래프있다.

② 주어지는 방향 그래프와 역방향을 가지는 역방향 그래프를 만든다.

③ 정점을 담을 스택을 만든다. 

코사라주는 위상정렬을 이용하고, 방향그래프와 역방향그래프가 동일한 SCC를 구성하는 것을 이용한다.

①-③ 까지 방향그래프, 역방향그래프, 스택을 준비한다.

순서는 아래와 같다. 

①② ③

1) ①방향그래프에 임의의 정점부터 DFS를 수행한다. DFS가 끝나는 순서대로 ③스택에 삽입한다. 

     1-1) DFS를 수행한 후 아직 방문하지 않은 정점이 있는 경우, 해당 정점부터 다시 DFS를 수행한다. 

     1-2) 모든 정점을 방문하여 DFS를 완료하여 스택에 모든 정점을 담는다.

2) 스택의 top 에서부터 pop을 하여 순서대로 ②역방향 그래프에서부터 DFS를 수행한다. 

     2-1) 이때 탐색되는 모든 정점을 SCC로 묶는다.

     2-2) 이 과정은 스택이 비어있을 때까지 진행한다.

     2-3) 만약 스택의 top에 위치한 정점이 이미 방문했다면 pop만 한다.

위 과정을 수행하면 주어진 그래프에서 SCC를 구할 수 있다. 

[예]

01234567891011121314151617181920

위와 같은 방향그래프가 있다고 할 때, SCC를 구해보자.

설명된 순서와 동일하게 ①방향그래프 ②역방향그래프 ③스택을 준비하자.

1) ①방향그래프에 임의의 정점부터 DFS를 수행한다. DFS 가 끝나는 순서대로 ③스택에 삽입한다.

[탐색조건] 여기서 방문하지 않은 정점을 찾는 조건을 둔다. 방문하지 않은 정점을 찾는 순서는 오름차순으로 번호가 낮은 정점부터 탐색한다.

그러면 1번 정점부터 탐색을 시작한다. 

이후 인접한 정점인 3번을 탐색한다.

 

3번 정점에서 인접한 정점은 5번, 6번 정점이 있는데 [탐색조건] 에 맞춰 5번정점부터 탐색한다.

그리고 5번정점에서 인접한 3번정점은 방문한 상태이므로, 6번 정점을 방문한다.

이후 6번정점에서 인접한 4번정점을 방문한다.

다음 4번정점에 인접한 2번정점을 방문한다.

이제 더이상 방문할 정점이 없으므로 DFS가 끝난 순서대로 스택에 삽입한다. 

과정 1)을 완료하였고, 이제 과정 2)를 진행한다.

2) 스택의 top 에서부터 pop을 하여 순서대로 ②역방향 그래프에서부터 DFS를 수행한다. 

     2-1) 이때 탐색되는 모든 정점을 SCC로 묶는다.

     2-2) 이 과정은 스택이 비어있을 때까지 진행한다.

     2-3) 만약 스택의 top에 위치한 정점이 이미 방문했다면 pop만 한다.

먼저 스택 TOP 에 위치한 1번 정점부터 ②역방향 그래프에서 DFS 탐색을 진행한다.

1번 정점에서는 다른 정점으로 DFS를 진행할 수 없으므로 1번 정점이 하나의 SCC가 된다.

다음으로 스택 TOP에 위치한 3번정점부터 DFS 탐색을 한다.

3번정점에 인접한 정점은 모두 같은 SCC가 된다. 

[탐색조건]에 따라 낮은 정점부터 DFS를 진행한다. 

1번정점은 이미 방문한 정점이므로 방문할 수 없다. 

2번정점을 방문한다. 

다음 4번정점을 방문한다.

다음 6번정점을 방문한다.

다음 5번정점을 방문한다.

3번정점부터 시작한 DFS 이 더 이상 방문할 정점이 없으므로 이것을 하나의 SCC로 묶는다.

스택에 있는 정점을 top부터 꺼내어 보면서 방문하지 않은 정점이 있는지 확인한다. 

이제 ②역방향 그래프 에서 모든 정점을 방문하였다.

그러면 ①방향그래프 는 2개의 SCC로 구성되어있음을 볼 수 있다.

BOJ-2150 : https://www.acmicpc.net/problem/2150

Strongly Connected Component 문제를 풀어보면 될 것 같다. 

코사라주로 구현한 BOJ-2150 코드는 http://wondy1128.tistory.com/28 을 참고하면 된다.