위상 정렬(Topological Sort)은 방향 비순환 그래프(DAG) 에서 각 정점을 의존성 순서에 맞게 일렬로 나열하는 알고리즘이다. 빌드 시스템, 작업 스케줄링, 패키지 의존성 해결에 활용된다.
동작 원리 (Kahn 알고리즘)
진입 차수(In-degree): 해당 정점으로 들어오는 간선 수
0 → 1 → 3 → 5
↓ ↑
2 → 4 ──┘
in-degree: {0:0, 1:1, 2:1, 3:2, 4:1, 5:1}
1. in-degree=0인 노드 큐에 삽입: [0]
2. 0 꺼내기 → 1,2의 in-degree 감소
3. 1,2 큐 삽입 → ...
결과: 0 → 1 → 2 → 4 → 3 → 5
구현
python
from collections import deque
def topological_sort(n, edges):
graph = [[] for _ in range(n)]
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque([i for i in range(n) if in_degree[i] == 0])
result = []
while queue:
node = queue.popleft()
result.append(node)
for next_node in graph[node]:
in_degree[next_node] -= 1
if in_degree[next_node] == 0:
queue.append(next_node)
if len(result) != n:
return None # 사이클 존재
return result
관련 개념
- •그래프 — DAG에만 적용
- •DFS — DFS 기반 위상 정렬도 가능
- •동적 프로그래밍 — DAG DP
참고문헌
- •Kahn, A.B. (1962). Topological sorting of large networks
