위상 정렬(topological sort)은 일반적으로 정렬하면 떠오르는 거품 정렬, 삽입 정렬, 선택 정렬, 힙 정렬, 퀵 정렬, 병합 정렬 등 비교 정렬(comparison sort)과는 다른 종류입니다. 위상 정렬은 사이클이 없는 방향 그래프(directed acyclic graph)에서 에지 <u, v>가 E(G)에 속할 때 반드시 정점 u가 정점 v에 앞서게 출력되는 정점의 나열을 의미합니다. 많은 책에서 위상 정렬을 설명할 때 할 일 목록을 예로 많이 듭니다. 해야 할 일을 쪼개 놓은 것을 정점이라 하고, 방향 간선에서 꼬리에 먼저 할 일을 기술해 놓고 그다음에 할 일을 머리에 둔다면 위상 정렬로 헷갈리지 않고 해야 할 일의 목록을 나열할 수 있습니다.

다음 그림으로 살펴보겠습니다.

▲ 그림 12-1 DAG