위상 정렬: 선행 조건을 지키는 순서를 만드는 방법
위상 정렬은 방향 그래프의 모든 간선 u→v에 대해 u가 v보다 앞에 오도록 정점을 나열하는 작업이다. 선수 과목, 작업 의존성, 빌드 순서를 처리할 때 쓰인다. 이런 순서는 방향 사이클이 없는 그래프인 DAG에서만 존재한다.
B와 C의 순서는 바뀔 수 있지만 모든 의존 간선은 앞선 정점에서 뒤의 정점으로 향한다.
들어오는 간선이 없는 작업부터 고르기
Kahn 알고리즘은 정점별 진입차수, 즉 아직 남아 있는 선행 조건의 수를 센다. 진입차수 0인 정점을 큐에 넣고 하나씩 출력한 뒤 그 정점의 outgoing 간선을 제거한 것으로 처리한다. 이웃의 진입차수가 0이 되면 실행 가능한 새 후보가 된다.
from collections import deque
def topological_order(graph):
incoming = {vertex: 0 for vertex in graph}
for neighbors in graph.values():
for neighbor in neighbors:
incoming[neighbor] += 1
ready = deque(v for v in graph if incoming[v] == 0)
order = []
while ready:
vertex = ready.popleft()
order.append(vertex)
for neighbor in graph[vertex]:
incoming[neighbor] -= 1
if incoming[neighbor] == 0:
ready.append(neighbor)
if len(order) != len(graph):
raise ValueError("Directed cycle exists")
return order
모든 이웃도 graph의 키로 등록되어 있다는 가정이다. 정점 수와 간선 수에 대해 시간 O(V+E), 추가 공간 O(V)다. 같은 방향 간선을 중복 저장했다면 차수를 셀 때와 줄일 때 모두 같은 횟수를 반영해야 한다.
여러 올바른 답이 있을 수 있다
프로그래밍 기초가 자료구조와 논리회로의 선수 조건이고, 자료구조가 알고리즘의 선수 조건이면 기초 이후 두 과목의 상대 순서는 고정되지 않을 수 있다. 진입차수 0 후보 중 무엇을 먼저 고르는지에 따라 다른 유효 순서가 나온다. 일정한 사전순 답이 필요하면 큐 대신 우선순위 큐를 쓰고 추가 비용을 고려한다.
모든 정점을 출력하기 전에 후보가 사라지면 남은 부분에는 사이클이 있다. A→B와 B→A라면 어느 것도 선행 조건을 모두 끝내지 못한다. 다만 출력되지 않은 모든 정점이 사이클 위에 있다는 뜻은 아니다. 사이클 뒤에 의존하는 정점도 함께 막힌다.
DFS의 종료 순서를 뒤집어도 DAG의 위상 순서를 얻을 수 있지만 사이클 여부를 함께 검증해야 한다. 단순한 방문 순서가 위상 정렬이라고 가정하면 의존성을 어길 수 있다.
위상 정렬은 가능한 선후 순서를 주며 작업별 실행 시간이나 자원 수까지 최적화하지는 않는다. 두 작업이 순서상 연속하더라도 의존성이 없다면 병렬 실행할 수 있다. 일정 계산에는 실행 시간, 자원, 가장 긴 의존 경로 같은 추가 정보가 필요하다.