유향 그래프에서 강연결 요소(SCC)를 선형 시간에 찾는 타잔 알고리즘의 개요, 핵심 아이디어, 의사코드, 시간·공간 복잡도 및 관련 참고문헌을 설명한다.
URL: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
위키백과, 우리 모두의 백과사전
Tarjan's strongly connected components algorithm
타잔 알고리즘 애니메이션
**타잔의 강연결 요소 알고리즘(Tarjan's strongly connected components algorithm)**은 그래프 이론에서 유향 그래프의 강연결 요소(SCC)를 찾는 알고리즘이다. 이 알고리즘은 선형 시간에 동작하며, 코사라주 알고리즘 및 경로 기반 강연결 요소 알고리즘을 포함한 다른 방법들의 시간 경계와 일치한다. 이 알고리즘은 발명자인 로버트 타잔의 이름을 땄다.[1]
이 알고리즘은 입력으로 유향 그래프를 받아, 그래프의 정점들을 강연결 요소들로 분할한 결과를 출력한다. 그래프의 각 정점은 정확히 하나의 강연결 요소에만 속한다. 어떤 정점이 유향 사이클 위에 있지 않다면 그 정점만으로 강연결 요소 하나를 이룬다. 즉, 진입 차수(in-degree) 또는 진출 차수(out-degree)가 0인 정점, 혹은 유향 비순환 그래프(DAG)의 모든 정점은 각각 단독으로 SCC가 된다.
알고리즘의 기본 아이디어는 다음과 같다. 깊이 우선 탐색(DFS)을 임의의 시작 노드에서 시작하고(그 뒤에는 아직 발견되지 않은 노드들에 대해 DFS를 추가로 수행한다). DFS의 일반적인 성질처럼, 탐색은 그래프의 각 노드를 정확히 한 번씩 방문하고 이미 방문한 노드는 다시 방문하지 않는다. 따라서 생성되는 탐색 트리들의 집합은 그래프의 스패닝 포리스트가 된다. 강연결 요소들은 이 포리스트의 특정한 부분 트리(subtree)들로서 복원된다. 이 부분 트리들의 뿌리 노드를 강연결 요소의 “루트(root)”라고 부른다. 어떤 SCC의 어느 노드든, 탐색에서 그 SCC 안에서 가장 먼저 발견되는 노드라면 루트가 될 수 있다.
깊이 우선 탐색 순회에 대해 어떤 강연결 요소의 루트는, DFS가 그 요소에서 처음으로 방문한 노드이다. 따라서 순회 도중 백트래킹(backtracking)으로 그 요소에서 빠져나올 때, 루트는 그 요소에서 마지막으로 되돌아 나오는 노드가 된다. 타잔 알고리즘의 핵심 아이디어는, 루트를 “이전에 방문했던 노드 중 어떤 것도 도달할 수 없는 노드”로도 표현할 수 있다는 점이다.
표준 DFS와 마찬가지로, 노드들은 방문되는 순서대로 스택에 쌓인다. 그러나 DFS와 달리, DFS가 어떤 노드 v 및 그 자손들을 재귀적으로 방문한 뒤에 이 재귀 호출이 반환된다고 해서 그 노드들이 모두 스택에서 반드시 빠지는 것은 아니다. 결정적인 불변식(invariant property)은 다음과 같다. 노드는 방문된 뒤에도, 입력 그래프에서 그 노드로부터 스택에서 더 앞(더 아래)에 있는 어떤 노드로 가는 경로가 존재하는 경우에만 스택에 남아 있다. 그리고 루트에서 백트래킹하며 빠져나올 때 노드들이 제거된다. 다시 말해, 어떤 노드는 자신과 연결된 모든 경로가 탐색될 때까지 DFS 스택에서 제거되지 않는다.
v와 그 자손들을 방문하는 호출이 끝날 때, v 자체가 스택에서 더 앞에 있는 어떤 노드로 가는 경로를 가지는지 여부를 알 수 있다. 만약 그렇다면, 불변식을 유지하기 위해 v는 스택에 남겨둔 채로 호출을 반환한다. 그렇지 않다면 v는 자신의 강연결 요소의 루트여야 하며, 그 SCC는 v와 스택에서 v보다 위(나중)에 있는 노드들로 이루어진다(그런 노드들은 모두 v로 되돌아가는 경로는 있지만, 더 앞선 노드로 가는 경로는 없다. 만약 더 앞선 노드로 가는 경로가 있었다면 v도 더 앞선 노드로 가는 경로가 있어야 하는데, 이는 거짓이기 때문이다). 그런 다음 v를 루트로 하는 연결 요소를 스택에서 꺼내(pop) 반환하여, 역시 불변식을 보존한다.
각 노드 v에는 고유한 정수 v.index가 할당되며, 이는 노드가 발견되는 순서대로 연속적으로 번호가 매겨진다. 또한 v.lowlink라는 값도 유지하는데, 이는 v의 DFS 부분 트리(자기 자신 v 포함)를 통해 v로부터 도달 가능한 것으로 알려진 스택 위 노드들 중 가장 작은 인덱스를 나타낸다. 따라서 v.lowlink < v.index이면 v는 스택에 남아 있어야 하고, v.lowlink == v.index이면 v는 강연결 요소의 루트로서 제거되어야 한다. v.lowlink 값은 v에서 시작하는 DFS 중에 계산되며, 이 탐색은 v로부터 도달 가능한 노드들을 찾아낸다.
lowlink는 lowpoint와 다르다. lowpoint는 그래프의 어느 부분이든 통해 v로부터 도달 가능한 인덱스 중 가장 작은 값이다.[1]: 156 [2]
algorithm tarjan is input: graph G = (V, E) output: set of strongly connected components (sets of vertices)
_index_ := 0
_S_ := empty stack
**for each** _v_ **in** _V_ **do**
**if** _v_.index is undefined **then**
strongconnect(_v_)
**function** strongconnect(_v_)
_// Set the depth index for v to the smallest unused index_
_v_.index := _index_
_v_.lowlink := _index_
_index_ := _index_ + 1
_S_.push(_v_)
_v_.onStack := true
_// Consider successors of v_
**for each** (_v_, _w_) **in** _E_ **do**
**if** _w_.index is undefined **then**
_// Successor w has not yet been visited; recurse on it_
strongconnect(_w_)
_v_.lowlink := min(_v_.lowlink, _w_.lowlink)
**else if** _w_.onStack **then**
_// Successor w is in stack S and hence in the current SCC_
_// If_w_is not on stack, then (_v_,_w_) is an edge pointing to an SCC already found and must be ignored_
_// See below regarding the next line_
_v_.lowlink := min(_v_.lowlink, _w_.index)
_// If v is a root node, pop the stack and generate an SCC_
**if** _v_.lowlink = _v_.index **then**
start a new strongly connected component
**repeat**
_w_ := _S_.pop()
_w_.onStack := false
add _w_ to current strongly connected component
**while** _w_ ≠ _v_
output the current strongly connected component
index 변수는 DFS 노드 번호 카운터이다. S는 노드 스택으로, 처음에는 비어 있으며 탐색되었지만 아직 어떤 강연결 요소로도 확정(commit)되지 않은 노드들의 이력을 저장한다. 이는 일반적인 DFS 스택이 아니다. 탐색이 트리를 따라 되돌아갈 때 노드가 pop되지 않고, 오직 하나의 SCC 전체가 발견되었을 때만 pop된다.
가장 바깥쪽 루프는 아직 방문되지 않은 각 노드를 탐색하여, 첫 번째 노드에서 도달 불가능한 노드들도 결국에는 모두 순회되도록 보장한다. strongconnect 함수는 노드 v에서 시작하는 그래프에 대해 단일 DFS를 수행하여, v에서 도달 가능한 모든 후속 정점(successor)을 찾고 그 부분 그래프의 모든 SCC를 보고한다.
각 노드가 재귀를 마칠 때, 해당 노드의 lowlink가 여전히 자신의 index로 설정되어 있다면 그 노드는 SCC의 루트 노드이며, 그 SCC는 스택에서 그 노드 위에 있는 모든 노드로 구성된다. 알고리즘은 스택에서 현재 노드까지(현재 노드 포함) pop한 뒤, 이 노드들을 하나의 SCC로 제시한다.
타잔의 논문에서는, w가 스택 위에 있을 때 v.lowlink를 v.lowlink := min(v.lowlink, w.index)로 갱신한다.[1]: 157 흔한 변형으로는 대신 v.lowlink := min(v.lowlink, w.lowlink)를 사용하기도 한다.[3][4] 이 수정된 알고리즘은 타잔이 정의한 의미 그대로의 lowlink 수를 계산하지는 않지만, 테스트 v.lowlink = v.index는 여전히 SCC의 루트 노드를 식별한다. 따라서 전체 알고리즘은 유효하게 유지된다.[2]
시간 복잡도: 타잔 절차는 각 노드에 대해 한 번 호출되며, forall 문은 각 간선을 많아야 한 번씩만 고려한다. 따라서 알고리즘의 실행 시간은 G의 간선과 노드 수에 대해 선형이며, 즉 (O(|V|+|E|))이다.
이 복잡도를 달성하려면 w가 스택 위에 있는지 여부를 상수 시간에 검사해야 한다. 의사코드처럼 각 노드에 “스택 위에 있는지”를 나타내는 플래그를 저장하고, 그 플래그를 확인하면 된다.
공간 복잡도: 타잔 절차는 각 정점마다 보조 데이터로 index와 lowlink 필드에 2워드, onStack에 1비트, 그리고 index가 정의되지 않았는지 판별하기 위한 또 다른 1비트를 필요로 한다. 또한 각 스택 프레임마다 v를 저장할 1워드와 간선 리스트에서의 현재 위치를 위한 1워드가 필요하다. 마지막으로 스택 S의 최악 크기는 (|V|)여야 한다(그래프가 하나의 거대한 구성요소일 때). 이를 종합하면 최종 분석은 (O(|V|\cdot (2+5w)))이며 여기서 (w)는 머신 워드 크기이다. Nuutila와 Soisalon-Soininen의 변형은 이를 (O(|V|\cdot (1+4w)))로 줄였고, 이어 Pearce의 변형은 (O(|V|\cdot (1+3w)))만 필요로 한다.[5][6]
각 강연결 요소 내부에서 노드들의 순서 자체에는 특별한 의미가 없지만, 알고리즘의 유용한 성질 하나는 어떤 SCC도 그 후속 SCC들보다 먼저 식별되지 않는다는 점이다. 따라서 SCC들이 식별되는 순서는, SCC들로 이루어진 DAG에 대한 역(Reverse) 위상 정렬이 된다.[7]
도널드 크누스는 자신의 책 _The Stanford GraphBase_에서 타잔의 SCC 알고리즘을 자신이 가장 좋아하는 구현 중 하나로 소개했다.[8]
그는 또한 다음과 같이 썼다.[9]
그가 이 문제를 위해 고안한 자료구조들은 놀라울 만큼 아름답게 맞물려 있어서, 유향 그래프를 탐색하는 동안 살펴봐야 하는 값들이 언제나 마치 마법처럼 손끝에 있다. 그리고 그의 알고리즘은 부산물로 위상 정렬도 수행한다.