위상 정렬
마지막 업데이트
방향 비순환 그래프(DAG)의 위상 정렬은 모든 간선 u → v에 대해 u가 v보다 앞에 오도록 정점을 선형으로 나열한 것입니다. 「모든 선행 조건이 먼저 끝나도록 이 작업들을 어떤 순서로 실행할 수 있는가?」와 같은 질문에 답합니다. 위의 재생을 눌러 칸 알고리즘이 정점을 유효한 순서로 하나씩 꺼내는 과정을 확인하세요.
칸 알고리즘은 남은 진입 간선이 없는 정점(진입 차수 0)을 반복적으로 꺼내 순서에 추가하고 그 나가는 간선을 제거합니다. 이로 인해 새로운 진입 차수 0 정점이 생길 수 있습니다. DAG에서만 작동합니다. 순환이 존재하면 일부 정점은 결코 진입 차수 0에 도달하지 못하고 유효한 순서가 존재하지 않습니다. 실행 시간은 O(V + E)입니다.
시간 및 공간 복잡도
| 측정 항목 | 복잡도 | 비고 |
|---|---|---|
| 시간 | O(V + E) | 각 정점은 한 번 출력되고, 각 간선은 한 번 제거됨 |
| 공간 | O(V) | 진입 차수 카운트 + 준비 집합 + 순서 |
| 필요 조건 | DAG | 순환에는 위상 정렬이 존재하지 않음 |
| 결과 | 유일하지 않음 | 여러 유효한 순서가 존재할 수 있음 |
단계별 (칸 알고리즘)
| 단계 | 무엇이 일어나는가 |
|---|---|
| 1 | 각 정점의 진입 차수(진입 간선 수)를 계산한다. |
| 2 | 진입 차수 0인 모든 정점을 준비 집합에 모은다. |
| 3 | 준비된 정점을 하나 꺼내 출력 순서에 추가한다. |
| 4 | 그 후속 정점 각각의 진입 차수를 감소시킨다. |
| 5 | 진입 차수 0에 도달한 후속 정점은 준비 집합에 합류한다. |
| 6 | 준비 집합이 빌 때까지 반복한다. |
풀이 예제
간선 A→C, B→C, C→D, C→E, D→F, E→F를 가진 DAG 정렬 (초기 진입 차수 A:0 B:0 C:2 D:1 E:1 F:2):
| 단계 | 준비 집합 | 순서 | 동작 |
|---|---|---|---|
| 0 | {A, B} | [] | A와 B는 진입 차수 0으로 시작하므로 둘 다 준비 완료. |
| 1 | {B} | [A] | A 출력. 간선 A→C가 C의 진입 차수를 2 → 1로 낮춤. |
| 2 | {C} | [A, B] | B 출력. 간선 B→C가 C를 1 → 0으로 낮춰 C가 준비 완료가 됨. |
| 3 | {D, E} | [A, B, C] | C 출력. 간선 C→D와 C→E가 D와 E를 0으로 낮춰 둘 다 준비 완료가 됨. |
| 4 | {E} | [A, B, C, D] | D 출력. 간선 D→F가 F의 진입 차수를 2 → 1로 낮춤. |
| 5 | {F} | [A, B, C, D, E] | E 출력. 간선 E→F가 F를 1 → 0으로 낮춰 F가 준비 완료가 됨. |
| 6 | {} | [A, B, C, D, E, F] | F 출력. 준비 집합이 비었고 6개 정점이 모두 정렬되어 완료. |
위상 정렬을 사용해야 할 때
| 사용할 때 | 피해야 할 때 |
|---|---|
| 의존 관계를 지키는 순서가 필요할 때(빌드 단계, 패키지 설치, 코스 선행 조건). | 그래프가 무방향일 때(위상 순서는 방향 그래프에 대해서만 정의됨). |
| 그래프가 DAG이고 유효한 선형 순서 아무 것이나 원할 때. | 그래프에 순환이 포함될 수 있는데도 전순서가 필요할 때(존재하지 않음). |
| 순환을 저렴하게 감지하고 싶을 때(실패한 위상 정렬은 순환의 존재를 증명함). | 어떤 가중치에 따른 최단 또는 최적 순서가 필요할 때. 단순 위상 정렬은 가중치를 무시함. |
순서를 O(V + E)로 한 번만 처리할 때. | 간선이 끊임없이 바뀌어 갱신마다 다시 정렬해야 할 때. 증분 구조가 더 적합함. |
Topological Sort 코드
Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 Topological Sort 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.
Python로 구현한 Topological Sort 코드
Python
1from collections import deque2
3
4def topological_sort(graph):5 # Kahn's algorithm: repeatedly remove nodes with no incoming edges6 in_degree = {node: 0 for node in graph}7 for node in graph:8 for neighbor in graph[node]:9 in_degree[neighbor] += 110 queue = deque(node for node in graph if in_degree[node] == 0)11 order = []12 while queue:13 node = queue.popleft()14 order.append(node)15 for neighbor in graph[node]:16 in_degree[neighbor] -= 117 if in_degree[neighbor] == 0:18 queue.append(neighbor)19 if len(order) != len(graph):20 raise ValueError("Graph has a cycle, no topological order")21 return order22
23
24graph = {25 "shirt": ["tie", "jacket"],26 "tie": ["jacket"],27 "pants": ["shoes", "jacket"],28 "socks": ["shoes"],29 "shoes": [],30 "jacket": [],31}32
33print(" -> ".join(topological_sort(graph)))JavaScript로 구현한 Topological Sort 코드
JavaScript
1const graph = {2 A: ["C"],3 B: ["C", "D"],4 C: ["E"],5 D: ["F"],6 E: ["F"],7 F: [],8};9
10// Kahn algorithm: repeatedly take a node with no incoming edges11function topologicalSort() {12 const inDegree = {};13 for (const node in graph) inDegree[node] = 0;14 for (const node in graph) {15 for (const next of graph[node]) inDegree[next]++;16 }17 const queue = Object.keys(inDegree).filter((n) => inDegree[n] === 0);18 const order = [];19 while (queue.length > 0) {20 const node = queue.shift();21 order.push(node);22 for (const next of graph[node]) {23 if (--inDegree[next] === 0) queue.push(next);24 }25 }26 if (order.length !== Object.keys(graph).length) {27 throw new Error("Graph has a cycle");28 }29 return order;30}31
32console.log("Topological order:", topologicalSort().join(" -> "));Java로 구현한 Topological Sort 코드
Java
1import java.util.ArrayDeque;2import java.util.List;3import java.util.Queue;4
5public class Main {6 public static void main(String[] args) {7 int n = 6;8 // DAG: an edge u -> v means u must come before v9 List<List<Integer>> adj = List.of(10 List.of(2),11 List.of(2, 3),12 List.of(4),13 List.of(4),14 List.of(5),15 List.of()16 );17 int[] inDegree = new int[n];18 for (List<Integer> next : adj) {19 for (int v : next) inDegree[v]++;20 }21
22 // Kahn: start from every node with no prerequisites23 Queue<Integer> queue = new ArrayDeque<>();24 for (int i = 0; i < n; i++) {25 if (inDegree[i] == 0) queue.add(i);26 }27
28 StringBuilder order = new StringBuilder("Topological order:");29 while (!queue.isEmpty()) {30 int node = queue.poll();31 order.append(" ").append(node);32 for (int next : adj.get(node)) {33 if (--inDegree[next] == 0) queue.add(next);34 }35 }36 System.out.println(order);37 }38}C++로 구현한 Topological Sort 코드
C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 // Directed acyclic graph: adj[u] lists nodes that depend on u7 std::vector<std::vector<int>> adj = {8 {}, // 09 {}, // 110 {3}, // 2 -> 311 {1}, // 3 -> 112 {0, 1}, // 4 -> 0, 113 {0, 2}, // 5 -> 0, 214 };15 int n = static_cast<int>(adj.size());16 std::vector<int> inDegree(n, 0);17 for (const auto& neighbors : adj) {18 for (int v : neighbors) ++inDegree[v];19 }20 // Kahn's algorithm: start from nodes with no incoming edges21 std::queue<int> ready;22 for (int u = 0; u < n; ++u) {23 if (inDegree[u] == 0) ready.push(u);24 }25 std::cout << "Topological order: ";26 while (!ready.empty()) {27 int u = ready.front();28 ready.pop();29 std::cout << u << " ";30 // Removing u unlocks neighbors whose in-degree drops to 031 for (int v : adj[u]) {32 if (--inDegree[v] == 0) ready.push(v);33 }34 }35 std::cout << "\n";36 return 0;37}C로 구현한 Topological Sort 코드
C
1#include <stdio.h>2
3#define N 64
5int main(void) {6 // Directed acyclic graph: adj[u][v] = 1 means an edge u -> v7 int adj[N][N] = {0};8 adj[2][3] = 1;9 adj[3][1] = 1;10 adj[4][0] = 1;11 adj[4][1] = 1;12 adj[5][0] = 1;13 adj[5][2] = 1;14 int inDegree[N] = {0};15 for (int u = 0; u < N; u++) {16 for (int v = 0; v < N; v++) inDegree[v] += adj[u][v];17 }18 // Kahn's algorithm: start from nodes with no incoming edges19 int queue[N];20 int head = 0, tail = 0;21 for (int u = 0; u < N; u++) {22 if (inDegree[u] == 0) queue[tail++] = u;23 }24 printf("Topological order: ");25 while (head < tail) {26 int u = queue[head++];27 printf("%d ", u);28 // Removing u unlocks neighbors whose in-degree drops to 029 for (int v = 0; v < N; v++) {30 if (adj[u][v] && --inDegree[v] == 0) queue[tail++] = v;31 }32 }33 printf("\n");34 return 0;35}위상 정렬 FAQ
위상 정렬은 어디에 사용되나요?
각 의존 대상이 그것을 필요로 하는 것보다 앞에 오도록 작업을 정렬합니다. 실제 용도로는 빌드 시스템과 패키지 관리자(의존성 먼저 컴파일), 선행 조건이 있는 코스 편성, 스프레드시트 수식 평가 순서 등이 있습니다.
위상 정렬의 시간 복잡도는 얼마인가요?
칸 알고리즘과 DFS 기반 접근법 모두
O(V + E) 시간에 실행됩니다. 각 정점이 한 번 처리되고 각 간선이 한 번 검사되기 때문입니다. 추가로 O(V) 공간을 사용합니다.위상 정렬은 왜 DAG를 필요로 하나요?
방향 순환은 모순을 만듭니다.
a가 b보다 앞에 와야 하고 b가 a보다 앞에 와야 한다면 어떤 선형 순서도 둘 다 만족할 수 없습니다. 따라서 위상 정렬은 그래프가 방향 비순환 그래프일 때, 오직 그때에만 존재합니다. 칸 알고리즘은 모든 정점을 출력하기 전에 종료되면 순환을 감지합니다.칸 알고리즘과 DFS 기반 위상 정렬의 차이는 무엇인가요?
칸 알고리즘은 반복적이며 BFS와 비슷합니다. 진입 차수 0인 정점을 반복적으로 제거하여 순환 감지와 순서 매기기를 완전히 명시적으로 만듭니다. DFS 접근법은 정점을 재귀적으로 방문하고 각 정점의 재귀가 끝날 때마다 순서의 앞에 추가하여 완료 시각의 역순을 만듭니다. 둘 다
O(V + E)입니다. 칸은 깊은 재귀를 피하고 준비 집합을 자연스럽게 드러내며, DFS는 대개 작성이 더 짧습니다.일반 정렬 대신 위상 정렬을 언제 사용해야 하나요?
순서가 비교 가능한 키가 아니라 항목 간 의존 관계로 정의될 때 위상 정렬을 사용합니다.
O(n log n) 병합 정렬 같은 비교 정렬은 값으로 정렬하지만, 위상 정렬은 「먼저 와야 한다」는 간선으로 정렬하며 비교 정렬과 달리 같은 입력에 대해 여러 유효한 답을 낼 수 있습니다.위상 정렬의 결과는 유일한가요?
보통은 그렇지 않습니다. 둘 이상의 정점이 동시에 준비 완료(진입 차수 0)될 때마다 임의의 순서로 출력할 수 있으므로 대부분의 DAG는 여러 유효한 위상 순서를 허용합니다. 순서는 각 단계에서 준비된 정점이 정확히 하나일 때만 유일하며, 이는 DAG가 단일 사슬(해밀턴 경로)을 이룰 때 발생합니다.
관련 자료
더 많은 시각화
