.png)
방향 그래프에서 임의의 두 정점 u, v 사이에 양방향 경로가 있을 때 두 정점은 같은 SCC(Strongly Connected Component) 에 속한다고 정의한다.
다음은 SCC의 예시이다.
같은 색으로 둘러싸여 있는 정점이 하나의 SCC 이다.
기본적으로 어떤 그래프에서 모든 SCC 를 찾아 분리하려면 모든 정점을 한 번씩 시작점으로 택하여 DFS를 실행한 다음, 모든 정점 쌍에 대해 양방향 경로가 존재하는지 조사하면 된다. 하지만 이렇게 하면 DFS를 실행하는데만 $\small O(V+E)$ 의 시간이 걸리는데 이를 정점 개수만큼 반복하므로 $\small O(VE)$ 또는 $\small O(V^2)$ 시간이 소요된다. 따라서 그래프의 크기가 조금만 커져도 많은 시간이 걸리게 된다.
그래프의 SCC를 선형 시간 안에 분리해주는 알고리즘이 존재한다. 범용적으로 ‘타잔 알고리즘(Tarjan’s Algorithm)’ 을 사용하고 간단히 구현할 때는 ‘코사라주 알고리즘(Kosaraju’s Algorithm)’ 을 사용한다. 이번 문서에서는 이 2개의 알고리즘을 살펴보도록 하자.
타잔의 알고리즘은 한 번의 DFS 만을 이용해 SCC를 분리해낸다. 타잔의 알고리즘은 이해하기도, 구현하기도 까다롭지만 그만큼 변형하기가 쉽고, DFS를 한 번만 사용하면 되므로 시간적인 이점이 크다는 점에서 코사라주 알고리즘보다 자주 사용된다.
타잔의 알고리즘은 “‘DFS 스패닝 트리’ 를 적절히 자르면 모든 SCC를 얻을 수 있다” 는 점에 착안한 알고리즘이다. 따라서 DFS 스패닝 트리가 무엇인지 알 필요가 있다.
DFS 스패닝 트리란 이름 그대로 DFS 를 이용해 만든 스패닝 트리이다. DFS는 한 번 방문한 정점을 다시 방문하지 않기 때문에 DFS에서 거치는 간선만 남기고 다른 간선을 제거하면 그 그래프의 스패닝 트리를 얻을 수 있다.
다음은 앞서 제시한 그래프를 1번 정점부터 DFS 했을 때 만들어지는 DFS 스패닝 트리이다.
.png)