해야 할 일을 순서에 상관없이 그리다 보니 그림 12-1과 같아졌다고 합시다. 이래서는 차례대로 어떤 일부터 해야 할지 잘 모르겠습니다. 이때 이 정점 순서를 간선 방향이 왼쪽에서 오른쪽으로만 이어지도록 나열하는 것을 위상 정렬이라고 합니다. 그림을 보면 이 그래프에는 특징이 몇 가지 있습니다. 먼저 방향 그래프고, 방향을 따라 정점을 이동했을 때 다시 자신에게 돌아오는 사이클이 존재하지 않습니다. 무방향 그래프와 달리 방향 그래프는 꼬리에서 머리로만 이동이 가능하기 때문에 4->2->3->1처럼 언뜻 보기에 사이클 같아 보이지만, 실제로 따라가 보면 움직일 수 없게 됩니다. 이처럼 방향 그래프이자 사이클이 없는 그래프를 DAG라고 합니다. 다른 특징으로는 그림 12-1의 그래프를 위상 정렬했을 때 정렬된 정점 순서가 유일하지 않습니다.

그림을 봅시다.

▲ 그림 12-2 여러 가지 DAG