타잔 알고리즘 편집하기

'''타잔 알고리즘'''(Tarjan's Algorithm)은 강한 연결 요소(SCC, Strongly Connected Components)를 찾는 알고리즘으로, 깊이 우선 탐색(DFS, Depth-First Search)을 기반으로 동작한다. 1972년 로버트 타잔(Robert Tarjan)에 의해 개발되었으며, O(V + E) 시간 복잡도를 갖는다.
==역사==
로버트 타잔은 1972년 논문 "Depth-first search and linear graph algorithms"에서 타잔 알고리즘을 발표하였다. 이후 이 알고리즘은 강한 연결 요소 탐색에서 널리 사용되며, 2-SAT 문제 해결, 네트워크 분석, 전자 회로 설계 등의 분야에서도 활용되고 있다.
==동작 방식 및 예제==
타잔 알고리즘은 DFS를 수행하면서 각 노드의 방문 순서(DFS 번호)와 최소 연결 가능 DFS 번호를 기록하며, 스택을 이용해 SCC를 찾는다. 기본적인 동작 과정은 다음과 같다.
*DFS를 수행하면서 각 노드에 대해 DFS 번호를 부여한다.
*방문한 노드를 스택에 저장하고, 현재 경로에서 가장 작은 DFS 번호를 유지한다.
*이미 방문한 노드를 다시 방문할 경우, 최소 DFS 번호를 갱신한다.
*DFS 탐색이 끝날 때, 현재 노드가 SCC의 루트라면 스택에서 해당 SCC를 구성하는 노드들을 꺼낸다.
'''예제'''

다음 그래프를 예로 들어 타잔 알고리즘이 어떻게 동작하는지 살펴보자.
  0 → 1
   ↖ 2
      ↓  
      3 → 4 → 6 
       ↖ ↓   ↓ ↖ 
          5   7 → 8  
이제 0번 노드에서 DFS를 시작한다고 가정하자.
#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
#방문한 노드를 스택에 저장하고 최소 DFS 번호를 유지한다.
#*3 → 4 방문 (DFS 번호: 4, 최소 DFS 번호: 4)
#*4 → 5 방문 (DFS 번호: 5, 최소 DFS 번호: 5)
#*5 → 3으로 되돌아가는데, 3은 스택에 있음 → 최소 DFS 번호 갱신 → 5의 최소 DFS 번호 = 3
#이미 방문한 노드를 다시 방문할 경우 최소 DFS 번호를 갱신한다.
#*5에서 DFS 종료 → 최소 DFS 번호 == DFS 번호이므로 SCC 찾음 → {3, 4, 5}
#DFS 탐색이 끝날 때 SCC를 찾고 스택에서 제거한다.
#*3, 4, 5가 SCC로 묶이며 스택에서 제거됨
#*2 → 0의 영향을 받아 최소 DFS 번호가 0으로 유지됨
#*0, 1, 2가 SCC로 묶이며 스택에서 제거됨
이제 아래 코드를 실행하여 동일한 결과를 확인할 수 있다.
==코드 예제==
<syntaxhighlight lang="python">
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))
</syntaxhighlight>
 출력 결과 예시:
 [[6, 8, 7], [3, 5, 4], [0, 2, 1]]
각 리스트는 하나의 SCC를 나타내며, 해당 그룹 내 모든 노드는 서로 도달 가능하다.
==시간 복잡도==
타잔 알고리즘의 시간 복잡도는 O(V + E)이며, 각 노드를 한 번 방문하고 각 간선을 한 번만 처리하기 때문에 선형적으로 동작한다.
==응용==
*방향 그래프에서 강한 연결 요소 탐색
*2-SAT 문제 해결
*웹 크롤링 및 네트워크 분석
*전자 회로에서 순환 종속성 탐색
==같이 보기==
*[[코사라주 알고리즘]]
*[[강한 연결 요소]]
*[[깊이 우선 탐색]]
==참고 문헌==
*Tarjan, R. (1972). "Depth-first search and linear graph algorithms". SIAM Journal on Computing, 1(2), 146–160.