선후 관계가 정해진 작업들을 순서대로 나열하는 것. A를 끝내야 B를 할 수 있다는 관계를 방향 간선으로 그린 그래프에서, 모든 관계를 어기지 않는 나열을 찾는다.
답이 하나가 아니다. 1, 3, 4, 6, 2, 5, 7도 되고 1, 4, 3, 6, 2, 5, 7도 된다. 가능한 순서 중 하나를 내놓는 것이 위상 정렬이다.
진입차수를 줄여가는 방법
가장 직관적이다. 진입차수가 0인 정점은 앞에 할 일이 남아 있지 않다는 뜻이니 지금 바로 시작할 수 있다.
진입차수가 0인 정점을 전부 큐에 넣고 시작한다. 큐에서 하나 꺼내 결과에 넣고, 그 정점에서 나가는 간선들을 보고 가리키는 정점의 진입차수를 1씩 줄인다. 간선을 실제로 지우지는 않지만 지운 것과 같다. 그러다 진입차수가 0이 된 정점이 있으면 큐에 넣고, 큐가 빌 때까지 반복한다. 복잡도는 O(V + E)다.
응용으로 사전순 가장 앞선 순서를 구하라는 문제가 자주 나온다. 큐를 우선순위 큐로 바꾸기만 하면 된다. 매 단계에서 지금 시작 가능한 것들 중 번호가 가장 작은 것을 꺼내게 되고, 그게 곧 사전순으로 가장 앞선 순서다.
DFS와 스택
DFS로 내려가다가 더 갈 곳이 없으면 그때 스택에 넣는다. 다 끝나고 스택을 꺼내면 그것이 위상 정렬 결과다. 먼저 끝난 것이 뒤에 오기 때문이다. 복잡도는 역시 O(V + E)다.
이쪽은 시작점 하나로 끝나지 않는다. 아직 방문하지 않은 정점이 남았으면 거기서 DFS를 새로 시작해야 하는데, 그 이유는 그래프에 적어두었다.
DAG라는 전제
두 경우에는 아예 정의되지 않는다. 무방향 그래프는 방향이 없으니 선후 관계가 없고, 사이클이 있는 그래프는 A 다음에 B, B 다음에 A라서 순서를 정할 수 없다.
방향이 있고 사이클이 없는 그래프(DAG)에서만 가능하다. 뒤집으면, 위상 정렬을 시도해서 실패하면 그 그래프에 사이클이 있다는 뜻이다.