타잔 알고리즘

타잔 알고리즘(Tarjan's Algorithm)은 강한 연결 요소(SCC, Strongly Connected Components)를 찾는 알고리즘으로, 깊이 우선 탐색(DFS, Depth-First Search)을 기반으로 동작한다. 1972년 로버트 타잔(Robert Tarjan)에 의해 개발되었으며, O(V + E) 시간 복잡도를 갖는다.

1 역사

로버트 타잔은 1972년 논문 "Depth-first search and linear graph algorithms"에서 타잔 알고리즘을 발표하였다. 이후 이 알고리즘은 강한 연결 요소 탐색에서 널리 사용되며, 2-SAT 문제 해결, 네트워크 분석, 전자 회로 설계 등의 분야에서도 활용되고 있다.

2 동작 방식 및 예제

타잔 알고리즘은 DFS를 수행하면서 각 노드의 방문 순서(DFS 번호)와 최소 연결 가능 DFS 번호를 기록하며, 스택을 이용해 SCC를 찾는다. 기본적인 동작 과정은 다음과 같다.

• DFS를 수행하면서 각 노드에 대해 DFS 번호를 부여한다.
• 방문한 노드를 스택에 저장하고, 현재 경로에서 가장 작은 DFS 번호를 유지한다.
• 이미 방문한 노드를 다시 방문할 경우, 최소 DFS 번호를 갱신한다.
• DFS 탐색이 끝날 때, 현재 노드가 SCC의 루트라면 스택에서 해당 SCC를 구성하는 노드들을 꺼낸다.

예제

다음 그래프를 예로 들어 타잔 알고리즘이 어떻게 동작하는지 살펴보자.

 0 → 1
  ↖ 2
     ↓  
     3 → 4 → 6 
      ↖ ↓   ↓ ↖ 
         5   7 → 8  

이제 0번 노드에서 DFS를 시작한다고 가정하자.

1. DFS를 수행하면서 DFS 번호를 부여한다.
   • 0번 노드 방문 → DFS 번호: 0, 최소 DFS 번호: 0
   • 1번 노드 방문 → DFS 번호: 1, 최소 DFS 번호: 1
   • 2번 노드 방문 → DFS 번호: 2, 최소 DFS 번호: 2
   • 2에서 다시 0번으로 가는데, 0은 이미 방문됨 → 최소 DFS 번호를 갱신 → 2의 최소 DFS 번호 = 0
   • 2에서 3번 노드로 이동 → DFS 번호: 3, 최소 DFS 번호: 3

1. 방문한 노드를 스택에 저장하고 최소 DFS 번호를 유지한다.
   • 3 → 4 방문 (DFS 번호: 4, 최소 DFS 번호: 4)
   • 4 → 5 방문 (DFS 번호: 5, 최소 DFS 번호: 5)
   • 5 → 3으로 되돌아가는데, 3은 스택에 있음 → 최소 DFS 번호 갱신 → 5의 최소 DFS 번호 = 3

1. 이미 방문한 노드를 다시 방문할 경우 최소 DFS 번호를 갱신한다.
   • 5에서 DFS 종료 → 최소 DFS 번호 == DFS 번호이므로 SCC 찾음 → {3, 4, 5}

1. DFS 탐색이 끝날 때 SCC를 찾고 스택에서 제거한다.
   • 3, 4, 5가 SCC로 묶이며 스택에서 제거됨
   • 2 → 0의 영향을 받아 최소 DFS 번호가 0으로 유지됨
   • 0, 1, 2가 SCC로 묶이며 스택에서 제거됨

이제 아래 코드를 실행하여 동일한 결과를 확인할 수 있다.

3 코드 예제

def tarjan_scc(graph):
    index = 0
    stack = []
    indices = {}
    lowlink = {}
    on_stack = set()
    sccs = []

    def strongconnect(node):
        nonlocal index
        indices[node] = index
        lowlink[node] = index
        index += 1
        stack.append(node)
        on_stack.add(node)

        for neighbor in graph[node]:
            if neighbor not in indices:
                strongconnect(neighbor)
                lowlink[node] = min(lowlink[node], lowlink[neighbor])
            elif neighbor in on_stack:
                lowlink[node] = min(lowlink[node], indices[neighbor])

        if lowlink[node] == indices[node]:
            scc = []
            while True:
                w = stack.pop()
                on_stack.remove(w)
                scc.append(w)
                if w == node:
                    break
            sccs.append(scc)

    for node in graph:
        if node not in indices:
            strongconnect(node)

    return sccs

# 예제 그래프 (방향 그래프)
graph = {
    0: [1],
    1: [2],
    2: [0, 3],
    3: [4],
    4: [5, 6],
    5: [3],
    6: [7],
    7: [8],
    8: [6]
}

# 강한 연결 요소 출력
print(tarjan_scc(graph))

출력 결과 예시:
[[6, 8, 7], [3, 5, 4], [0, 2, 1]]

각 리스트는 하나의 SCC를 나타내며, 해당 그룹 내 모든 노드는 서로 도달 가능하다.

4 시간 복잡도

타잔 알고리즘의 시간 복잡도는 O(V + E)이며, 각 노드를 한 번 방문하고 각 간선을 한 번만 처리하기 때문에 선형적으로 동작한다.

5 응용

• 방향 그래프에서 강한 연결 요소 탐색
• 2-SAT 문제 해결
• 웹 크롤링 및 네트워크 분석
• 전자 회로에서 순환 종속성 탐색

6 같이 보기

• 코사라주 알고리즘
• 강한 연결 요소
• 깊이 우선 탐색

7 참고 문헌

• Tarjan, R. (1972). "Depth-first search and linear graph algorithms". SIAM Journal on Computing, 1(2), 146–160.