위상 정렬은 방향 비순환 그래프에서 모든 간선 u→v에 대해 u가 v보다 앞서도록 정점을 나열하는 것이다.
원리
진입 차수가 0인 정점을 반복 제거하거나 DFS 종료 순서를 이용한다. 가능한 순서는 하나가 아닐 수 있다.
그래프 알고리즘 |
|---|
너비 우선 탐색 · 깊이 우선 탐색 · 다익스트라 알고리즘 · 벨만 포드 알고리즘 · 플로이드 워셜 알고리즘 |
예시
작업 B가 A의 결과를 필요로 하면 A→B로 표현한다. 위상 순서에 따라 실행 계획을 세우면 선행 작업이 뒤에 놓이지 않는다.
주의할 점
방향 사이클이 있으면 위상 정렬은 불가능하다. 결과가 모든 정점을 포함했는지 확인해야 하며, 위상 순서가 작업의 최적 병렬 스케줄을 자동으로 정하지는 않는다.