위상 정렬로 의존성 작업 순서 설계하기
DAG 위상 정렬의 원리와 사이클 검출 방식을 정리하고, DFS 및 Kahn 알고리즘 구현과 운영상 선택 기준을 다룬다.
2026-08-14 · 최초 발행 2024-04-29
간선이 요구하는 순서를 선형 목록으로 바꾸기
위상 정렬(Topological Sort)은 유향 비순환 그래프(DAG)의 정점을 간선 방향에 맞춰 나열하는 절차다. 간선 u→v가 있으면 결과 목록에서 u는 반드시 v보다 앞에 놓인다.
그래프에 사이클이 있으면 이 조건을 만족하는 순서는 만들 수 없다. 그래서 구현은 순서를 생성하는 일과 함께 사이클을 감지해야 한다. 또한 DAG라 해도 결과가 하나로 고정되지는 않는다. 같은 시점에 처리 가능한 노드가 있다면 처리 정책에 따라 서로 다른 유효 순서가 나올 수 있으며, 우선순위 큐나 정렬을 적용하면 일관된 결과를 만들 수 있다.
DFS와 진입차수 방식이 사이클을 다루는 법
DFS 기반 구현은 정점의 상태를 미방문, 방문 중, 방문 완료로 관리한다. 탐색 중인 정점으로 다시 들어가는 백엣지를 발견하면 사이클이다. 한 정점의 모든 이웃 방문이 끝난 뒤 결과에 넣고, 최종 결과를 뒤집어 위상 순서를 얻는다.
Kahn 알고리즘은 각 정점의 진입차수에서 출발한다. 진입차수가 0인 정점을 큐에서 꺼내고, 그 정점에서 나가는 간선을 제거하면서 새로 진입차수가 0이 된 정점을 추가한다. 처리가 끝났을 때 처리된 정점 수가 전체 정점 수보다 작으면 사이클이 남아 있다는 뜻이다.
두 방식의 공통 시간 복잡도는 O(V+E), 공간 복잡도는 O(V+E)다. DFS에서는 재귀 스택 비용을 고려해야 하고, Kahn 알고리즘에서는 indegree 배열과 큐 비용을 고려한다. 깊은 그래프는 DFS의 재귀 제한 이슈가 있을 수 있는 반면, Kahn 알고리즘은 너비 중심 처리라 대규모 그래프와 스트리밍 환경에서 다루기 직관적이고 병렬화 여지도 확보하기 쉽다.
DFS 후위 순회로 순서 만들기
입력은 정점 수 n과 간선 목록 edges(u→v)다. 인접 리스트를 만든 뒤 상태 배열을 0(미방문)/1(방문 중)/2(방문 완료)로 관리한다. DFS 중 1 상태의 정점으로 진입하면 실패 처리하고, 방문이 완료된 정점을 결과 스택에 넣은 뒤 역순으로 반환한다.
전제조건: Python 3.10+, 정점 ID: 0..n-1
# Python 3.10+
from typing import List, Tuple
def topo_sort_dfs(n: int, edges: List[Tuple[int, int]]) -> List[int]:
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
state = [0] * n # 0=unvisited, 1=visiting, 2=done
order: List[int] = []
has_cycle = False
def dfs(u: int) -> None:
nonlocal has_cycle
state[u] = 1
for v in graph[u]:
if state[v] == 0:
dfs(v)
if has_cycle:
return
elif state[v] == 1:
has_cycle = True
return
state[u] = 2
order.append(u)
for u in range(n):
if state[u] == 0:
dfs(u)
if has_cycle:
break
if has_cycle:
raise ValueError("Cycle detected: DAG required")
order.reverse()
return order
if __name__ == "__main__":
n = 6
edges = [(5,2),(5,0),(4,0),(4,1),(2,3),(3,1)]
print(topo_sort_dfs(n, edges))진입차수를 줄여 가는 Kahn 알고리즘
Kahn 알고리즘은 인접 리스트와 각 정점의 진입차수를 계산한 뒤, indegree=0 정점을 큐에 넣는다. 큐에서 꺼낸 정점의 간선을 따라 진입차수를 줄이고, 값이 0이 된 정점을 다시 큐에 넣는다. 모든 정점이 처리되면 위상 순서를 반환하고, 그렇지 않으면 사이클로 실패한다.
전제조건: Python 3.10+, 정점 ID: 0..n-1
# Python 3.10+
from collections import deque
from typing import List, Tuple
def topo_sort_kahn(n: int, edges: List[Tuple[int, int]]) -> List[int]:
graph = [[] for _ in range(n)]
indeg = [0] * n
for u, v in edges:
graph[u].append(v)
indeg[v] += 1
q = deque([u for u in range(n) if indeg[u] == 0])
order: List[int] = []
while q:
u = q.popleft()
order.append(u)
for v in graph[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
if len(order) != n:
raise ValueError("Cycle detected: DAG required")
return order
if __name__ == "__main__":
n = 6
edges = [(5,2),(5,0),(4,0),(4,1),(2,3),(3,1)]
print(topo_sort_kahn(n, edges))그래프 특성에 따른 구현 선택
| 지표 | DFS 기반 | 큐 기반(Kahn) |
|---|---|---|
| 성능(시간) | O(V+E), 상수항 작음 | O(V+E), 대규모에서도 안정 |
| 성능(공간) | O(V+E) + 재귀 스택 O(h) | O(V+E) + 큐/indegree O(V) |
| 확장성 | 깊은 그래프에서 재귀 제한 이슈 가능 | 너비 중심 처리, 대규모/스트리밍 적합 |
| 일관성(결과 안정성) | 방문 순서 의존, 우선순위 적용 시 결정성 확보 | 큐 정책에 의존, 우선순위 큐로 결정성 확보 |
| 안정성(실패 모드) | 스택 오버플로우 가능성, 백엣지로 사이클 검출 | 처리 수 부족으로 사이클 검출, 예외 명확 |
| 운영 편의 | 구현 간결, 디버깅 시 호출 스택 추적 용이 | 진입차수 관리 명확, 증분 업데이트 용이 |
대규모 파이프라인, 빌드, 데이터 마이그레이션처럼 병렬 실행과 의존성 상태 확인이 중요한 환경에서는 Kahn 알고리즘이 맞는다. 메모리와 깊이 제약이 낮고 빠르게 구현해야 하는 경우에는 DFS도 유효하다. 어느 쪽이든 결과 재현성이 요구되면 동위 노드의 tie-breaking 정책을 명시해야 한다.
의존성 그래프가 등장하는 작업
빌드 시스템에서는 소스와 타깃 사이의 의존 그래프를 위상 정렬해 컴파일과 링크 순서를 정한다. 병렬 빌드에서는 indegree=0 정점 집합을 워커에 분배할 수 있다.
데이터베이스 마이그레이션에서는 foreign key 제약을 고려해 테이블 생성·삭제·변경 순서를 구하고, 롤백에는 그 역순을 적용한다. DAG 기반 데이터 파이프라인(Airflow 등)과 잡 스케줄링에서는 태스크 실행 순서와 동시성을 관리하며, 장애가 발생했을 때 해결되지 않은 의존성을 추적하기 쉽다.
컴파일러의 AST/IR 변환 단계 간 선후 관계를 보장하거나, 교육 커리큘럼의 선수 과목 그래프에서 수강 가능 순서를 계산하는 문제도 같은 구조를 사용한다.
순서 계산이 운영에 주는 효과
O(V+E)로 대규모 의존성을 해석하면 기존 순차/브루트포스 대비 3~10배 단축할 수 있으며, 그래프 밀도와 구현 최적화에 따라 결과는 달라진다. 사이클을 일찍 찾아내면 런타임 데드락과 무한 대기를 막고 배포 실패율을 낮출 수 있다.
indegree=0 집합을 병렬 실행하면 리소스 활용률을 높일 수 있고, 워크플로 처리량은 클러스터 자원 상황에 따라 20~50% 개선될 수 있다. 결정적 tie-breaking 정책은 빌드와 파이프라인 결과의 재현성을 높여 디버깅 비용을 줄인다.