Topological Sort: 방향 그래프의 선후 관계를 순서로 풀어내는 정렬
위상 정렬(Topological Sort)은 방향 비순환 그래프(DAG)에서 정점 간 선후 관계를 위배하지 않는 선형 순서를 찾는 알고리즘이다. 진입 차수(in-degree) 기반의 칸(Kahn) 알고리즘과 DFS 기반 알고리즘 두 가지 방식이 대표적이며, 빌드 시스템의 의존성 해석이나 작업 스케줄링처럼 순서가 중요한 실무 문제에 직접 적용된다. 순환(cy
1. 개념
위상 정렬은 방향 비순환 그래프(Directed Acyclic Graph, DAG)의 모든 정점을 정점 간 간선 방향을 거스르지 않도록 일렬로 나열하는 것이다. 간선 u → v가 존재하면 정렬 결과에서 u는 반드시 v보다 앞에 온다.
DAG가 아니면(즉 순환이 존재하면) 위상 정렬은 불가능하다. 순환이 있다는 것은 서로가 서로의 선행 조건이 되는 모순 상태이기 때문이다.
같은 그래프라도 위상 정렬 결과는 유일하지 않을 수 있다. 여러 개의 유효한 순서가 동시에 존재할 수 있다.
2. 왜 사용하는가
현실의 많은 문제가 "A를 하기 전에 B를 먼저 해야 한다"는 선후 관계로 모델링된다.
- 대학 수강 신청: 선수 과목을 먼저 이수해야 한다.
- 빌드 시스템: 모듈 A가 모듈 B에 의존하면 B를 먼저 컴파일해야 한다.
- 패키지 매니저: 의존성 그래프를 해석해 설치 순서를 정한다.
- 작업 스케줄링: 태스크 간 선행 조건을 만족하는 실행 순서를 정한다.
이런 문제를 그래프로 모델링하면 위상 정렬 알고리즘 하나로 일반화해서 풀 수 있다. 또한 위상 정렬을 시도했는데 모든 정점을 처리하지 못하면, 그 자체로 순환 의존성이 존재한다는 증거가 되므로 순환 탐지 도구로도 활용된다.
3. 동작 원리
3.1 칸(Kahn) 알고리즘 — BFS 기반
- 모든 정점의 진입 차수(in-degree, 자신을 가리키는 간선 수)를 계산한다.
- 진입 차수가 0인 정점(선행 조건이 없는 정점)을 큐에 넣는다.
- 큐에서 정점을 하나 꺼내 결과 리스트에 추가한다.
- 그 정점에서 나가는 간선을 모두 제거한다. 즉 인접한 정점들의 진입 차수를 1씩 감소시킨다.
- 진입 차수가 0이 된 정점을 큐에 추가한다.
- 큐가 빌 때까지 3~5를 반복한다.
- 결과 리스트의 길이가 전체 정점 수보다 적으면, 사이클이 존재해 위상 정렬이 불가능하다.
3.2 DFS 기반 알고리즘
- 방문하지 않은 정점에서 DFS를 시작한다.
- 현재 정점에서 갈 수 있는 모든 인접 정점을 먼저 재귀적으로 방문한다.
- 더 이상 갈 곳이 없는 정점(즉 후위 순회에서 마지막으로 처리 완료되는 정점)을 스택에 push한다.
- 모든 정점의 방문이 끝나면 스택을 순서대로 pop하여 나열한 것이 위상 정렬 결과다.
DFS 방식에서는 "탐색 완료(모든 후손을 다 처리) 순서의 역순"이 위상 정렬 결과가 된다는 점이 핵심이다. 순환 탐지는 DFS 진행 중인 경로(방문 중 상태)에 다시 도달하는지로 판단한다.
4. 코드 예제
from collections import deque, defaultdict
def topological_sort_kahn(num_vertices, edges):
"""
칸 알고리즘 (BFS 기반)
edges: (u, v) 리스트, u -> v 방향 (u가 v보다 선행)
반환: 위상 정렬 결과 리스트. 사이클이 있으면 None
"""
graph = defaultdict(list)
in_degree = [0] * num_vertices
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque(v for v in range(num_vertices) if in_degree[v] == 0)
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(result) != num_vertices:
return None # 사이클 존재 -> 위상 정렬 불가능
return result
def topological_sort_dfs(num_vertices, edges):
"""
DFS 기반 위상 정렬
반환: 위상 정렬 결과 리스트. 사이클이 있으면 None
"""
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GRAY, BLACK = 0, 1, 2 # 미방문, 방문 중(경로 상), 방문 완료
state = [WHITE] * num_vertices
stack = []
has_cycle = False
def dfs(node):
nonlocal has_cycle
state[node] = GRAY
for neighbor in graph[node]:
if state[neighbor] == GRAY:
has_cycle = True
return
if state[neighbor] == WHITE:
dfs(neighbor)
if has_cycle:
return
state[node] = BLACK
stack.append(node)
for v in range(num_vertices):
if state[v] == WHITE:
dfs(v)
if has_cycle:
return None
return stack[::-1]
if __name__ == "__main__":
# 예: 0 -> 1 -> 3, 0 -> 2 -> 3 (다이아몬드 형태 의존성)
n = 4
edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
print(topological_sort_kahn(n, edges)) # 예: [0, 1, 2, 3]
print(topological_sort_dfs(n, edges)) # 예: [0, 2, 1, 3]
# 사이클이 있는 경우
cyclic_edges = [(0, 1), (1, 2), (2, 0)]
print(topological_sort_kahn(3, cyclic_edges)) # None5. 시간 복잡도 또는 성능 특성
정점 수를 V, 간선 수를 E라 할 때 두 알고리즘 모두 다음과 같다.
- 시간 복잡도: O(V + E)
- 칸 알고리즘: 모든 정점을 큐에 한 번씩 넣고 빼며, 모든 간선을 정확히 한 번씩 순회하며 진입 차수를 감소시킨다. - DFS 알고리즘: 모든 정점과 간선을 한 번씩 방문한다.
- 공간 복잡도: O(V + E)
- 인접 리스트 저장에 O(V + E), 진입 차수 배열 또는 방문 상태 배열에 O(V), 큐/스택에 O(V).
두 알고리즘의 시간 복잡도는 동일하지만 실무에서는 용도에 따라 선택이 갈린다. 칸 알고리즘은 사이클 탐지가 자연스럽고(결과 개수 비교만 하면 됨) 반복문 기반이라 스택 오버플로 위험이 없다. DFS 방식은 재귀 깊이가 정점 수만큼 깊어질 수 있어 큰 그래프에서는 재귀 한도(recursion limit) 문제를 조심해야 한다.
6. 실무 사용 사례
- 패키지 매니저 의존성 해석: npm, pip, apt 등은 패키지 간 의존 관계를 그래프로 만들고 위상 정렬로 설치 순서를 결정한다.
- 빌드 시스템: Make, Bazel, Webpack 같은 도구는 모듈/타겟 간 의존성을 위상 정렬해 컴파일·번들링 순서를 정한다.
- 작업 스케줄러 / CI 파이프라인: 여러 단계(job)가 서로 선행 조건을 가질 때 실행 순서를 계산한다.
- 스프레드시트 수식 계산 순서: 셀 A가 셀 B를 참조하면 B를 먼저 계산해야 하므로, 셀 간 참조 관계를 그래프로 만들어 재계산 순서를 정한다.
- 컴파일러의 심볼 해석: 타입이나 클래스 정의 간 의존 관계를 순서대로 해석할 때 사용한다.
-- 참고: 실제로는 그래프 알고리즘을 애플리케이션 코드에서 수행하는 경우가 많지만,
-- 재귀 CTE로 계층적 의존성 데이터를 조회하는 예시 (선행 작업 목록 확장)
WITH RECURSIVE task_dependencies AS (
SELECT task_id, depends_on, 1 AS depth
FROM task_edges
WHERE task_id = 'deploy'
UNION ALL
SELECT te.task_id, te.depends_on, td.depth + 1
FROM task_edges te
JOIN task_dependencies td ON te.task_id = td.depends_on
)
SELECT DISTINCT depends_on, depth
FROM task_dependencies
ORDER BY depth DESC;7. 주의할 점
- 입력이 DAG인지 먼저 검증: 사이클이 있으면 위상 정렬 자체가 정의되지 않는다. 칸 알고리즘에서는 결과 리스트 길이가 정점 수보다 작은지로, DFS에서는 방문 중(GRAY) 상태의 정점을 다시 만나는지로 확인한다.
- 결과의 비유일성: 진입 차수가 0인 정점이 동시에 여러 개면 처리 순서에 따라 다른 결과가 나온다. 특정 순서를 보장하려면 큐 대신 우선순위 큐를 사용하는 등 추가 규칙이 필요하다.
- 재귀 DFS의 스택 오버플로: 정점 수가 수만 개 이상인 그래프에서 재귀 DFS를 쓰면 언어별 재귀 한도에 걸릴 수 있다. 이 경우 반복문 기반(명시적 스택)으로 바꾸거나 칸 알고리즘을 쓰는 것이 안전하다.
- 끊어진 그래프(비연결 그래프): 모든 정점을 순회하며 미방문 정점마다 DFS를 새로 시작해야 한다. 시작 정점 하나에서만 DFS를 돌리면 일부 정점이 누락된다.
- 자기 자신을 향하는 간선(self-loop): 이 자체가 사이클이므로 진입 차수 계산 시 반드시 반영해야 한다.
8. 핵심 정리
위상 정렬은 DAG에서 선후 관계를 지키는 정점 나열 순서를 O(V + E)에 구하는 알고리즘이며, 칸 알고리즘(진입 차수 기반 BFS)과 DFS 기반 알고리즘 두 방식이 있다. 결과가 유일하지 않을 수 있고, 사이클이 있으면 정렬이 불가능하다는 성질을 이용해 순환 의존성 탐지에도 활용한다. 빌드 시스템, 패키지 매니저, 작업 스케줄링처럼 "먼저 해야 할 일"이 존재하는 실무 문제 대부분이 이 알고리즘으로 환원된다.