위상 정렬 (Topological Sort)
빠른 설명
위상 정렬(Topological Sort)은 방향 비순환 그래프(DAG, Directed Acyclic Graph)에서 모든 간선의 방향을 지키도록 정점을 나열하는 알고리즘이다.
즉, 간선 A → B가 있다면 항상 A가 B보다 먼저 출력된다.
언제 쓰는가
- 선수 과목(Prerequisite) 문제
- 작업(Task)들의 수행 순서를 정할 때
- 빌드(Build) 순서 결정
- 의존성(Dependency) 해결
- DAG 위에서 DP를 수행할 때
위상 정렬이 불가능한 경우는
- 방향 사이클(Cycle) 이 존재하는 경우
- 자기 자신으로 향하는 간선(Self Loop) 이 있는 경우 (사이클의 특수한 형태)
시간복잡도
- 그래프 생성:
- 위상 정렬:
- 전체:
참고자료
- CP-Algorithms - Topological Sorting
- Wikipedia - Topological sorting
- GeeksforGeeks - Topological Sorting
- 나무위키 - 위상 정렬
C++ 코드
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> topological_sort(int n, const vector<vector<int>>& graph) {
vector<int> indegree(n + 1, 0);
// 진입 차수 계산
for (int i = 1; i <= n; i++) {
for (int next : graph[i]) {
indegree[next]++;
}
}
queue<int> q;
// 진입 차수가 0인 정점을 큐에 삽입
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0)
q.push(i);
}
vector<int> order;
while (!q.empty()) {
int now = q.front();
q.pop();
order.push_back(now);
for (int next : graph[now]) {
indegree[next]--;
if (indegree[next] == 0)
q.push(next);
}
}
return order;
}
int main() {
int n = 6;
vector<vector<int>> graph(n + 1);
graph[1].push_back(2);
graph[1].push_back(3);
graph[2].push_back(4);
graph[3].push_back(4);
graph[4].push_back(5);
graph[5].push_back(6);
vector<int> result = topological_sort(n, graph);
for (int x : result)
cout << x << ' ';
}Python 코드
from collections import deque
def topological_sort(n, graph):
indegree = [0] * (n + 1)
# 진입 차수 계산
for i in range(1, n + 1):
for nxt in graph[i]:
indegree[nxt] += 1
q = deque()
# 진입 차수가 0인 정점 삽입
for i in range(1, n + 1):
if indegree[i] == 0:
q.append(i)
order = []
while q:
now = q.popleft()
order.append(now)
for nxt in graph[now]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
q.append(nxt)
return order
n = 6
graph = [[] for _ in range(n + 1)]
graph[1].append(2)
graph[1].append(3)
graph[2].append(4)
graph[3].append(4)
graph[4].append(5)
graph[5].append(6)
print(topological_sort(n, graph))