위상 정렬

위상 정렬이란

위상 정렬(topological sort)은 방향 그래프의 정점을 모든 간선 u → v에 대해 u가 v보다 앞에 오도록 한 줄로 나열하는 것이다. 다시 말해 각 정점은 자기가 의존하는 정점이 모두 나온 뒤에야 나온다.

사이클이 있으면 「u가 v보다 앞, v가 u보다 앞」이 동시에 필요해져 순서가 없다. 그래서 위상 정렬은 방향 비순환 그래프(DAG) 에서만 존재하고, 거꾸로 위상 정렬이 실패하면 사이클이 있다는 뜻이다.
답은 하나가 아닐 수 있다. 서로 의존하지 않는 정점끼리는 순서를 바꿔도 된다.

쓰는 곳	정점	간선
작업 스케줄링	작업	x를 끝내야 y를 시작할 수 있다
선수 과목	과목	선수 과목 → 수강 과목
빌드·패키지 설치 순서	모듈·패키지	의존 대상 → 의존하는 쪽
스프레드시트 재계산, 번들러 모듈 평가 순서	셀·모듈	참조 대상 → 참조하는 쪽

칸 알고리즘: 진입 차수와 큐

칸(Kahn) 알고리즘은 들어오는 간선이 없는 정점(진입 차수 0)부터 꺼낸다. 의존하는 것이 없으니 지금 바로 처리해도 된다.

모든 정점의 진입 차수를 센다.
진입 차수가 0인 정점을 모두 큐에 넣는다.
큐에서 정점을 꺼내 결과에 붙이고, 그 정점에서 나가는 간선을 지운다(이웃의 진입 차수를 1 줄인다). 이웃의 진입 차수가 0이 되면 큐에 넣는다.
큐가 빌 때까지 반복한다. 결과 길이가 정점 수보다 짧으면 사이클이 있다. 사이클 위의 정점은 진입 차수가 끝내 0이 되지 않기 때문이다.

from collections import deque
 
def topo_sort(n, edges):            # edges: (선행, 후행) 쌍
    graph = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indeg[v] += 1
 
    queue = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    return order if len(order) == n else None   # None = 사이클

간선을 어느 방향으로 저장했는지가 가장 흔한 실수다. 「과목 a를 들으려면 b가 필요하다」가 [a, b]로 주어지면 간선은 b → a다.

DFS로 구하기

DFS에서 한 정점의 탐색이 끝나는 순간(후위 순서) 그 정점을 기록하면, 그 정점에서 갈 수 있는 정점은 모두 먼저 기록된다. 그래서 후위 순서를 뒤집으면 위상 순서가 된다.

사이클 판별에는 방문 상태를 셋으로 나눈다.

상태	뜻
미방문	아직 들어가지 않았다
방문 중	현재 재귀 경로 위에 있다
완료	탐색이 끝나 결과에 기록됐다

탐색 중에 방문 중인 정점을 다시 만나면 현재 경로로 돌아오는 간선(back edge)이 있다는 뜻이므로 사이클이다. 방문 여부를 참·거짓 두 상태로만 두면 이미 끝난 정점과 경로 위 정점을 구별하지 못해 사이클이 아닌 곳에서도 사이클로 판정한다.

두 방법 비교

	칸 알고리즘	DFS 후위 순서
자료구조	진입 차수 배열 + 큐	재귀(또는 스택) + 3상태 방문 배열
사이클 판별	결과 길이 < 정점 수	방문 중인 정점을 다시 만남
단계별 처리	큐를 레벨 단위로 비우면 「동시에 할 수 있는 작업 묶음」과 최소 학기 수를 얻는다	어렵다
재귀 깊이	문제없다	정점이 많으면 스택 한도에 걸린다

둘 다 모든 정점과 간선을 한 번씩 보므로 O(V + E)다.

변형

사전순으로 가장 앞선 순서: 큐 대신 최소 힙을 쓴다. 진입 차수가 0인 정점 중 번호가 가장 작은 것부터 꺼낸다. O((V + E) log V).
모든 작업을 끝내는 최소 시간: 작업마다 걸리는 시간이 있으면, 위상 순서대로 훑으며 끝나는 시각[v] = max(끝나는 시각[u]) + 시간[v]를 갱신한다. DAG 위의 DP이고, 가장 긴 경로가 임계 경로(critical path)다.
위상 순서가 유일한가: 칸 알고리즘 도중 큐에 정점이 둘 이상 들어 있는 순간이 있으면 순서가 여러 개다.

정리

위상 정렬 = DAG의 정점을 의존 관계를 지키며 한 줄로 세우기. 사이클이 있으면 불가능하다.
칸 알고리즘은 진입 차수 0인 정점부터 큐로 꺼내고, 결과 길이로 사이클을 판별한다.
DFS는 후위 순서를 뒤집고, 방문 중 상태를 다시 만나면 사이클이다.
둘 다 O(V + E). 사전순 최소는 힙, 최소 완료 시간은 위상 순서 DP로 푼다.

버그 제보

위상 정렬

위상 정렬이란

칸 알고리즘: 진입 차수와 큐

DFS로 구하기

두 방법 비교

변형

정리

댓글