강한 연결 요소(SCC) 구현 톺아보기

• 강한 연결 요소란?
• 코사라주-샤리르 알고리즘
• 타잔 알고리즘
• 개보 알고리즘

강한 연결 요소란?

방향 있는 그래프^digraph $G = (V, E)$의 각 정점 $u \in V$에서 다른 모든 정점 $v \in V \setminus \{u\}$에 도달할 수 있다면 $G$는 강하게 연결되어 있다^{Strongly Connected}고 합니다. $G$의 연결된 부분 그래프, 즉 연결 요소 $H$가 강하게 연결되어 있을 때, $H$를 강한 연결 요소^{Strongly Connected Component}라고 합니다.

그래프를 가장 적은 수의 강한 연결 요소로 분할하는 알고리즘을 일반적으로 강한 연결 요소 알고리즘이라 부릅니다. 정점이나 간선을 더 추가할 수 없는(극대^maximal) 강한 연결 요소는 서로 겹치지 않기 때문에 이러한 분할은 유일합니다. 그래프를 강한 연결 요소로 분할하고, 강한 연결 요소에 속하는 정점들을 하나의 정점으로 묶은 그래프를 그래프의 응축^condensation이라고 하며, 응축된 그래프는 사이클이 존재하지 않아 위상 정렬이 가능하고, 동적 계획법을 쉽게 적용할 수 있습니다.

이 글에서는 깊이 우선 탐색을 사용하는 세 가지 대표적인 강한 연결 요소 알고리즘을 소개합니다. 세 가지 알고리즘 모두 선형 시간 $\mathcal{O}(V+E)$에 동작합니다.

도달 가능성 판정을 사용하는 병렬 강한 연결 요소 알고리즘도 기회가 된다면 써 보고 싶습니다.

코사라주-샤리르 알고리즘

그래프 $G$의 각 간선의 방향을 뒤집은 전치 그래프^{Transpose Graph} $G^\top$를 생각해 봅니다. $G$의 강한 연결 요소와 $G^\top$의 강한 연결 요소는 같을 것입니다.

이제 $G$에서 각 정점을 모두 둘러보고 이전 정점으로 돌아가는 시점을 생각해 봅니다. 서로 다른 강한 연결 요소 $A$, $B$가 있을 때, 반드시 $A$를 모두 둘러보고 $B$를 모두 둘러보거나, 그 반대임을 알 수 있습니다. 여기서 임의로 $A$를 먼저 둘러보고 $B$를 둘러보게 된다고 가정하면, $B$에서 $A$로 가는 간선이 존재한다는 말이 됩니다. $G^\top$에서는 이 간선의 방향이 반대이므로, $B$에서 깊이 우선 탐색을 시작하면 $A$에 도달할 수 없다는 결론을 얻게 됩니다.

그런데 같은 강한 연결 요소에 속하는 정점끼리는 $G$와 $G^\top$ 모두에서 서로에게 도달 가능하기 때문에, $G$에서 깊이 우선 탐색이 나중에 끝난 정점부터 $G^\top$에서 깊이 우선 탐색을 하게 되면 강한 연결 요소를 하나씩 얻을 수 있습니다.

전체 그래프에 대해 깊이 우선 탐색을 정방향과 역방향으로 두 번 실행하기 때문에, 시간 복잡도는 $\mathcal{O}(V + E)$가 됩니다.

이 알고리즘에서 가장 먼저 얻은 강한 연결 요소는 $G$에서 가장 처음에 둘러보기 시작하는 연결 요소라는 점도 생각해 보면 좋습니다. 코사라주-샤리르 알고리즘은 강한 연결 요소를 위상 정렬했을 때, 가장 처음에 오는 연결 요소부터 얻어냅니다.

타잔 알고리즘

다양한 그래프 알고리즘을 개발한 Robert E. Tarjan의 아이디어로, 전체 그래프에 대해 단 한 번의 깊이 우선 탐색을 통해 강한 연결 요소를 구할 수 있습니다. Tarjan이 개발한 알고리즘은 여럿 있으나 한국에서는 강한 연결 요소를 구하는 알고리즘을 가리켜 타잔 알고리즘이라 부르는 것으로 보입니다.

$G$의 강한 연결 요소를 위상 정렬해 보겠습니다. 가장 마지막에 오는 강한 연결 요소는 다른 연결 요소들과 전혀 연결되어 있지 않습니다. 따라서 이 연결 요소 안에 있는 모든 정점에서 깊이 우선 탐색을 시작한 시점은 연속되어 있습니다. 이 연결 요소에 속하는 모든 정점을 제외하고 나면, 남은 연결 요소 중 마지막에 오는 것도 깊이 우선 탐색을 시작한 시점이 연속되어 있을 것입니다. 어느 정점에서 연결 요소가 시작되는지, 끝나는지를 알면 스택을 이용하여 같은 연결 요소에 속하는 정점들을 연속되게 관리할 수 있을 것으로 보입니다.

강한 연결 요소 $A$에 속하는 정점 중 처음 탐색하게 되는 정점 $u_A$를 생각해 봅시다. $u_A$와 연결된 정점은 $A$에 속하는 정점이거나, $A$보다 나중에 오는 강한 연결 요소 $B$에 속한 정점입니다. 알고리즘이 올바르다면 $B$에 속한 정점들은 $A$보다 먼저 처리되어 스택에서 사라질 것이므로, $A$에 속한 다른 정점들과 $u_A$만을 구분하여 다른 정점들은 스택에 남기고, $u_A$의 탐색이 끝날 때 $A$에 속한 모든 정점을 스택에서 꺼내올 방법이 필요합니다. $A$에 속한 다른 정점들은 모두 $u_A$에 도달하는 방법이 존재하고, 다른 정점들을 탐색할 때 $u_A$는 스택에 존재한다는 사실을 이용할 수 있습니다.

각 정점 $u$마다 $u$에서 도달할 수 있으면서 스택에서 가장 일찍 쌓인 정점 $\ell_u$를 관리합시다. $u$의 탐색이 끝날 때 $u = \ell_u$라면 $u = u_A$입니다. 스택에서 $u$까지의 정점을 모두 삭제하고 새로운 강한 연결 요소에 배정하면 됩니다.

간선 $(u, v)$를 확인할 때, $v$를 아직 방문하지 않았다면 $v$를 방문한 후에 $\ell_u$를 $\min(\ell_u, \ell_v)$로 갱신합니다. $\ell_v$는 $u$에서도 도달할 수 있으므로 자연스럽습니다. $v$를 이미 방문했다면 $v$는 스택에 있을 수도 있고 없을 수도 있습니다. $v$가 스택에 있는 경우에도 $\ell_u$를 $\min(\ell_u, \ell_v)$로 갱신해야 합니다.^* $v$가 이미 방문했는데도 스택에 없다면 다른 강한 연결 요소에 속하는 정점이어서 처리가 완료된 것이므로 $\ell_u$를 갱신할 필요가 없습니다.

* Tarjan의 원본 논문에서는 $\min(\ell_u, v)$로 되어 있는데, 두 방법 모두 결과에 영향을 미치지 않습니다.

전체 그래프에서 깊이 우선 탐색을 한 번 수행하고, 각 정점에 스택에서 한 번씩만 추가되고 삭제되므로 전체 시간 복잡도는 $\mathcal{O}(V+E)$입니다.

각 정점을 방문했는지, 스택에 현재 존재하는지를 관리하기 위해 $1$비트씩 필요하고, $\ell$을 저장하는 데 단어^word 크기 $w$비트가 필요합니다. 깊이 우선 탐색을 수행하는 과정에서 정점과 간선 번호를 저장한다고 가정하면 전체 그래프가 강하게 연결된 경우에 총 $2wV$ 비트가 필요합니다. 이때 스택 또한 크기가 $V$이므로 위 알고리즘을 그대로 구현하면 총 $(4w+2)V$ 비트가 필요합니다. Pearce가 이를 개선하여 현재는 $(3w+1)V$ 비트를 요구하는 알고리즘이 알려져 있습니다. 해당 구현체는 여기를 클릭해서 확인하실 수 있습니다.

개보 알고리즘

마지막으로 설명할 알고리즘은 Gabow의 알고리즘으로, 경로 기반 강한 연결 요소 알고리즘^{Path-based Strong Components Algorithm}의 일종입니다. 이 분류에는 여러 알고리즘이 속하고, 최초로 보고된 선형 알고리즘은 Dijkstra(1976)이지만, Gabow(2000)가 단순하고 범용적이어서 소개해 보려고 합니다.

타잔 알고리즘과 같이, 스택 $S$에서 같은 연결 요소에 있는 정점을 연속되게 관리합니다.$\ell$을 저장하는 대신, 각 정점 $u$마다 $S[p] = u$가 되는 $p$를 저장해 둡니다. $S$에 $u$가 없을 수도 있는데, 이 경우는 따로 처리합니다.

동시에, 각 강한 연결 요소에서 처음 만나는 정점 $u$마다 $p_u$를 스택 $B$로 관리해 줍니다. 처음에 $p_u$는 $u$로 정하고, $u$의 탐색이 끝날 때 $p_u = \mathrm{top}(B)$이면 정의에 따라 $S$에 저장된 정점들을 모두 삭제하고 새로운 연결 요소에 배정하면 됩니다.

간선 $(u, v)$를 탐색할 때, $p_v$가 존재하면서 $p_v \lt \mathrm{top}(B)$라는 것은 $u$에서 $v$로 도달할 수 있으면서 스택에 $v$부터 $u$까지 이르는 경로가 존재한다는 뜻입니다. 이 정점들은 모두 같은 연결 요소에 속해야 하므로 조건을 만족하지 않을 때까지 $B$의 맨 마지막 원소를 제거해 줍니다. $p_v$가 존재하지 않는 경우는 아직 $v$를 한 번도 방문하지 않았거나 $v$가 이미 강한 연결 요소에 배정된 경우뿐입니다. 후자의 경우 추가적인 처리가 필요하지 않으므로 무시해도 됩니다.

전체 그래프에서 깊이 우선 탐색을 한 번 하고, 스택 $S$와 $B$에서 각 정점이 한 번씩 추가되고 삭제되므로 시간복잡도는 $\mathcal{O}(V + E)$입니다.

이상으로 세 가지 강한 연결 요소 알고리즘을 소개해 보았습니다. 세 알고리즘 모두 문제의 접근 방식과 해결 방법이 아름다운 것 같습니다. 이 글이 그래프에 대한 이해를 조금 더 깊게 할 수 있었으면 좋겠습니다.

틀린 내용이나 추가할 내용 등이 있는 경우 댓글로 알려주시면 감사하겠습니다.