타잔(Tarjan) 알고리즘이란?
타잔(Tarjan) 알고리즘은 방향 그래프(directed graph)에서 강한 연결 요소(Strongly Connected Component, SCC)를 찾는 데 사용되는 대표적인 그래프 알고리즘입니다. 이 알고리즘의 가장 큰 장점은 단 한 번의 DFS(깊이 우선 탐색)만으로 그래프 내 모든 강한 연결 요소를 구할 수 있다는 점입니다.
DFS 탐색을 수행하면 그래프의 DFS 트리(포레스트)를 얻을 수 있습니다. 이 DFS 트리로부터 강한 연결 요소들을 도출하게 되며, 어떤 서브트리의 루트가 발견되면 해당 서브트리 전체를 하나의 강한 연결 요소로 출력할 수 있습니다.
핵심 아이디어
타잔 알고리즘은 탐색 과정에서 각 정점에 대해 다음 정보를 유지합니다.
- disc[]: 정점이 발견된 순서(발견 시간)
- low[]: 해당 정점에서 도달 가능한 정점 중 가장 작은 발견 시간
- 스택(stack): 현재 탐색 경로에 있는 정점들을 저장
- stackItemFlag[]: 각 정점이 스택에 포함되어 있는지 여부를 추적
탐색 중 low[u] == disc[u]가 성립하는 순간, 정점 u는 하나의 강한 연결 요소의 루트입니다. 이때 스택에서 u가 나올 때까지 정점들을 차례로 꺼내어 출력하면, 그 집합이 곧 하나의 강한 연결 요소가 됩니다.
입력 및 출력
입력: 그래프의 인접 행렬 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 출력: 강한 연결 요소: 4 3 1 2 0
알고리즘
findComponent(u, disc, low, stack, stackItemFlag)
입력: 시작 노드 u, 발견 시간을 저장할 disc 배열, 서브트리 정보를 담을 low 배열, 정점을 보관할 스택, 스택 포함 여부를 추적하는 stackItemFlag 배열
출력: 강한 연결 요소(SCC)를 화면에 출력
Begin
time := 0 // time 값은 다음 함수 호출 시 초기화되지 않음(static)
set disc[u] := time+1 and low[u] := time + 1
time := time + 1
push u into stack
stackItemFlag[u] := true
for all vertex v which is adjacent with u, do
if v is not discovered, then
findComponent(v, disc, low, stack, stackItemFlag)
low[u] = minimum of low[u] and low[v]
else if stackItemFlag[v] is true, then
low[u] := minimum of low[u] and disc[v]
done
poppedItem := 0
if low[u] = disc[u], then
while u is not in the stack top, do
poppedItem := top of stack
display poppedItem
stackItemFlag[poppedItem] := false
pop item from stack
done
poppedItem := top of stack
display poppedItem
stackItemFlag[poppedItem] := false
pop item from stack
EndstrongConComponent(graph)
입력: 주어진 그래프
출력: 그래프의 모든 강한 연결 요소
Begin
initially set all items in the disc array to undiscovered
for all elements in low to φ
and mark no item is stored into the stack
for all node i in the graph, do
if disc[i] is undiscovered, then
findComponent(i, disc, low, stack, stackItemFlag)
EndC++ 구현 예제
#include<iostream>
#include<stack>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
{0, 0, 1, 1, 0},
{1, 0, 0, 0, 0},
{0, 1, 0, 0, 0},
{0, 0, 0, 0, 1},
{0, 0, 0, 0, 0}
};
int min(int a, int b) {
return (a<b)?a:b;
}
void findComponent(int u, int disc[], int low[], stack<int>&stk, bool stkItem[]) {
static int time = 0;
disc[u] = low[u] = ++time; // 발견 시간과 low 값 초기화
stk.push(u);
stkItem[u] = true; // u가 스택에 있음을 표시
for(int v = 0; v<NODE; v++) {
if(graph[u][v]) {
if(disc[v] == -1) { // v를 아직 방문하지 않은 경우
findComponent(v, disc, low, stk, stkItem);
low[u] = min(low[u], low[v]);
} else if(stkItem[v]) // v가 스택에 있는 경우, u의 low 값 갱신
low[u] = min(low[u], disc[v]);
}
}
int poppedItem = 0;
if(low[u] == disc[u]) { // u가 SCC의 루트인 경우
while(stk.top() != u) {
poppedItem = stk.top();
cout << poppedItem << " ";
stkItem[poppedItem] = false; // 팝된 항목으로 표시
stk.pop();
}
poppedItem = stk.top();
cout << poppedItem << endl;
stkItem[poppedItem] = false;
stk.pop();
}
}
void strongConComponent() {
int disc[NODE], low[NODE];
bool stkItem[NODE];
stack<int> stk;
for(int i = 0; i<NODE; i++) { // 모든 배열 초기화
disc[i] = low[i] = -1;
stkItem[i] = false;
}
for(int i = 0; i<NODE; i++) // 아직 방문하지 않은 노드에서 탐색 시작
if(disc[i] == -1)
findComponent(i, disc, low, stk, stkItem);
}
int main() {
strongConComponent();
}실행 결과
4 3 1 2 0
시간 복잡도
타잔 알고리즘은 각 정점과 간선을 정확히 한 번씩 처리하므로 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점의 수, E는 간선의 수를 의미합니다. 두 번의 DFS를 필요로 하는 코사라주(Kosaraju) 알고리즘과 달리, 타잔 알고리즘은 한 번의 DFS만으로 SCC를 구할 수 있어 실무에서도 널리 활용됩니다.