1. 위상정렬이란?
위상정렬은 유향 그래프(digraph; directed graph)에서 간선(edge)의 방향을 거스르지 않도록 정점(vertex)을 나열하는 것을 의미합니다.
https://ko.wikipedia.org/wiki/위상정렬
위상정렬 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예
ko.wikipedia.org
예를 들어 위와 같은 유향 그래프가 있을 때, 다음과 같이 정점을 [1, 2, 6, 3, 4, 5, 7]로 정렬하면 간선의 방향을 거스르지 않으면서 정렬됩니다. 이는 위상 정렬의 한 예입니다.
위상 정렬의 결과는 유일하지 않습니다.
위의 결과에서 6을 첫 번째 위치로 옮기거나, 5를 세 번째 위치로 옮겨도 간선의 방향을 거스르지 않고 위상 정렬을 만족하는 것을 알 수 있습니다.
2. 비순환 방향 그래프(DAG; Directed Acyclic Graph)
위상 정렬을 하기 위한 조건이 있습니다.
바로 그래프가 비순환 방향 그래프(DAG; Directed Acyclic Graph)여야 합니다.
즉, 사이클이 없어야 합니다.
위와 같이 사이클이 존재하는 그래프는 정점을 어떻게 정렬하더라도 간선의 방향을 거스르게 된다는 것을 알 수 있습니다.
따라서 위상 정렬을 하기 위해서는 반드시 비순환 방향 그래프여야만 합니다.
3. 첫 번째 위상 정렬 알고리즘(우선순위 큐 활용)
위에서 살펴본 그래프로 위상 정렬하는 방법을 살펴봅시다.
먼저, 우선순위 큐를 활용하여 정렬하는 방법이 있습니다.
위와 같이 그래프가 존재할 때, 각 정점에 진입하는 간선의 개수(진입 차수, indegree)를 확인합니다.
간선의 개수가 작은 것을 우선으로 하는 우선순위 큐에 정점들을 담습니다.
우선순위 큐에서 정점 하나를 꺼내면 진입 차수가 0인 정점이 나옵니다.
이 때, 진입 차수가 0으로 같은 정점 중에 어떤 정점이 나와도 상관 없습니다.
(위상 정렬의 결과가 여러 개 생길 수 있다는 말과 같습니다.)
편의 상 진입 차수가 같으면 정점의 값이 크기가 작은 것을 우선으로 하겠습니다.
해당 정점과 연결된 간선을 삭제하고 진입 차수를 수정합니다.
위 과정을 반복하며 제거한 정점을 순서대로 나열하면 위상 정렬이 완료됩니다.
4. 두 번째 위상 정렬 알고리즘(스택 활용, DFS 응용)
위상 정렬을 하는 두 번째 알고리즘은 깊이 우선 탐색(DFS; Depth First Search)와 과정이 완벽히 같습니다.
정점 1 부터 탐색을 시작해봅시다.
더 이상 연결되는 간선이 없는 정점에 도달할 때까지 탐색을 계속하면, 7번 정점, 3번 정점 순으로 탐색이 완료됩니다.
2번 정점에서 깊이 우선 탐색으로 4번 정점을 탐색하면, 연결된 7번 정점은 이미 방문했으므로 4번 정점이 세 번째로 탐색이 완료됩니다.
위 과정으로 깊이 우선 탐색을 하며 탐색을 마친 정점을 차례대로 스택에 담으면 아래와 같이 됩니다.
스택에 담겨있는 정점을 차례로 꺼내서 순서대로 배열하면 아래와 같은 위상 정렬이 완료됩니다.
