프로그래밍 대회를 위한 알고리즘 [1] – Tarjan’s Algorithm

본 포스팅은 geeksforgeeks의 http://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/ 를 통해 제작된 것입니다.

 

알고리즘 설명

Tarjan’s Algorithm은 그래프에서 Strongly Connected Component (SCC)를 찾아내기 위한 알고리즘이다. 여기에서 SCC란 유향간선(양방향 통로가 아닌 단방향 통로)으로 구성된 그래프 중에서도 모든 정점 쌍 사이에 경로가 존재하는 그래프를 말한다. 예를 들어 아래의 그래프에서는 그림과 같이 3개의 SCC가 존재한다.

Tarjan’s algorithm은 다음과 같은 사실들에 근거한다.

  1. DFS 탐색은 DFS 트리를 만들어낸다.
  2. SCC는 DFS의 subtree를 구성한다.
  3. 만약 그러한 subtree의 head를 찾을 수 있다면, 해당 subtree의 모든 노드를 출력할 수 있다.
  4. 하나의 SCC로부터 다른 SCC로 돌아가는 back edge는 존재하지 않는다. (서로 다른 SCC는 사이클을 이루지 않는다는 말인 듯.)

 

SCC의 head를 찾기 위해서 disc와 low 배열을 사용한다. disc[u]는 탐색에서 u를 방문한 시간이며, low[u]는 u를 root로 한 subtree에서 도달할 수 있는 가장 일찍 방문된 정점의 방문 시간을 의미한다.

즉, 어떤 SCC의 head란 disc[u] == low[u]인 노드를 의미한다. SCC에 속한 다른 노드의 경우 disc[u] > low[u]이다.

알고리즘의 동작은 다음과 같다.

  • 그래프 G에서 아직 방문하지 않은 노드 u를 하나 선택한다.
    • 노드 u를 Stack에 집어 넣는다.
    • dist[u] = 현재 노드를 방문하는 시간, low[u] = dist[u]
    • u로부터 이동가능한 SCC에 속하지 않은 노드 v를 탐색한다.
      • 만약 방문하지 않은 노드라면 해당 노드로 DFS를 호출한 후에 low[u] = min(low[u], low[v]) 이다.
      • 만약 이미 방문한 노드라면 low[u] = min(low[u], disc[v])이다.
    • 탐색 종료 후 disc[u] = low[u]이면
      • 노드 u는 SCC의 Head이다.
      • Stack에서 u까지를 pop하여 SCC를 구성한다.

이 알고리즘은 모든 노드를 모든 엣지를 통해서 단 한번만 방문하기 때문에 O(V + E)의 시간 복잡도를 갖는다.

 

코드 (원본 : geeksforgeeks)

 

 

Leave a Reply

Next ArticleCodeforces educational round 32