한양과기고 에듀테크 수업도구 대시보드

강한 연결 요소 — Tarjan 알고리즘

방향 그래프에서 서로가 서로를 (간선을 따라) 왔다 갔다 할 수 있는 노드 묶음을 강한 연결 요소(SCC, Strongly Connected Component) 라고 부릅니다. Tarjan 알고리즘은 DFS를 딱 한 번 돌면서 각 노드에 disc(발견 순서)와 low(자신이 되돌아갈 수 있는 가장 이른 조상)라는 두 값만으로 이 묶음들을 찾아냅니다. 아래에서 다음 단계 버튼을 눌러 한 걸음씩 따라가 보세요.

Tarjan 알고리즘 한 단계씩 실행

Tarjan 스택 (LIFO)

스택에 남은 노드는 아직 어느 SCC 에도 확정되지 않았어요.

disc / low

확정된 SCC

A 에서 DFS 를 시작합니다. ▶ 다음 단계 를 눌러 진행하세요.

트리 간선(첫 방문) 역방향 간선(back edge, low 갱신 유발) 스택에 있음 SCC 확정

low-link 값이 하는 일

disc — 발견 순서

DFS 가 그 노드를 몇 번째로 방문했는지 (타임스탬프)
한 번 정해지면 절대 바뀌지 않음
스택에 push 하며 함께 기록

low — 되돌아갈 수 있는 최솟값

자신 또는 자손이 역방향 간선으로 닿을 수 있는 가장 이른 disc
자식 DFS 가 끝나면 low[u]=min(low[u], low[v])
역방향 간선을 만나면 low[u]=min(low[u], disc[v])
low[u] == disc[u] 이면 u 가 그 SCC 의 뿌리 — 스택에서 u 까지 통째로 꺼냄

Tarjan vs Kosaraju

항목	Tarjan	Kosaraju
DFS 횟수	1번	2번 (원본 1번 + 역방향 그래프 1번)
핵심 아이디어	low-link 값으로 그 자리에서 판별	완료 시간 역순 + 그래프 뒤집기
부가 자료구조	스택 1개, `onStack` 플래그	역방향 인접 리스트, 완료 순서 스택
시간 복잡도	`O(V + E)` — 둘 다 선형

어디에 쓰일까요? 컴파일러의 순환 의존성 탐지, 소셜 그래프의 맞팔 커뮤니티 찾기, 2-SAT 문제 풀이, 웹 크롤러의 상호 링크 클러스터 파악 등에 쓰입니다. SCC 하나를 노드 하나로 뭉치면 사이클이 없는 축약 그래프(condensation DAG) 가 되어, 이후 위상 정렬 같은 알고리즘을 그대로 적용할 수 있습니다.

파이썬 의사 코드

# graph[u] = [u 에서 나가는 방향 간선의 도착 노드들] disc, low, on_stack, stack = {}, {}, {}, [] timer = 0 sccs = [] def tarjan(u): global timer disc[u] = low[u] = timer; timer += 1 stack.append(u); on_stack[u] = True for v in graph[u]: if v not in disc: # 트리 간선 — 아직 못 가본 곳 tarjan(v) low[u] = min(low[u], low[v]) elif on_stack.get(v): # 역방향 간선 — 스택에 남아있는 조상 low[u] = min(low[u], disc[v]) if low[u] == disc[u]: # u 가 SCC 의 뿌리! comp = [] while True: w = stack.pop(); on_stack[w] = False comp.append(w) if w == u: break sccs.append(comp)

학습용 인터랙티브 페이지 · 한양과학기술고등학교 프로젝트 허브