위상 정렬(topological sort)
Last updated
Last updated
위상 정렬이란 뱡향있는 그래프 내 정점들의 선형 순서를 이용하여 정렬하는 것을 뜻한다. 위상정렬이 가능하려면 그래프는 DAG(Directed Acyclic Graph)여야 한다.
위상 정렬에서는 정점을 2가지로 분류 한다.
소스(source) - 안으로 들어오는 간선이 없는 정점
싱크(sink) - 밖으로 나가는 간선이 없는 정점
위 DAG에서 소스는 정점 A와 G이며 싱크는 정점 F다.
위상정렬 과정은 아래와 같다.
싱크를 찾는다.
결과 리스트에 삽입한다.
찾은 싱크와 싱크로 들어오는 간선을 그래프에서 삭제한다.
그래프가 빌 때 까지 1 ~ 3 을 반복한다.
위 그림의 경우 5 -> 4 -> 2 -> 3 -> 1 순서로 정점이 그래프에서 삭제되므로 위상정렬의 결과는
1 -> 3 -> 2 -> 4 -> 5 가 될 것이다. 그렇다면 그래프에서 어떻게 싱크를 찾을 수 있을까?
임의의 정점에서 출발하여 더 이상 다른 정점으로 이동할 수 없는 정점까지 간선을 타고 이동한다.
정점을 매번 이동할 때는 해당 정점이 이전에 방문했던 정점으로 향하는 간선을 가지고 있지 않은지 확인한다. 즉, 그래프에 사이클이 있는지 확인한다. 사이클이 있다면 정렬을 할 수 없기 때문이다.
위상정렬의 시간복잡도는 얼마나 될까? 아래와 같은 DAG가 있다고 가정하자.
A0에서 출발하여 정점 A3까지 이동 후 A3을 삭제한다.
A0에서 출발하여 정점 A2까지 이동 후 A2를 삭제한다.
A0에서 출발하여 정점 A1까지 이동 후 A1을 삭제한다.
A0을 삭제한다.
싱크를 찾아서 삭제하는 과정이 1번 발생할 때마다 그래프 내 모든 정점을 탐색하므로 이 때의 시간복잡도는 O(|V|)이다. 싱크를 찾아서 삭제하는 과정은 정점의 갯수만큼 발생하므로 시간복잡도는 O(|V| * |V|) = O(|V| ^ 2) 이다. 즉, 정점의 갯수의 제곱이 시간복잡도가 되는 것이다.
그러나 그래프의 정점의 갯수가 매우 많다면 시간복잡도가 O(|V|^2)인 정렬은 매우 느린 알고리즘이 될 것이다. 따라서 그래프에서 싱크를 삭제하기 위해 매번 첫 정점에서부터 이동을 시작하지 않고, 삭제된 싱크 바로 이전의 정점으로 상태를 되돌리는 방법을 사용한다. 즉, DFS를 사용한다.
위 코드는 DFS와 post_time을 이용하여 아래의 그래프를 위상 정렬한다.
과정은 아래와 같다.
그래프 전체를 DFS하면서 각 정점의 post_time을 기록한다.
가장 큰 post_time을 가진 정점이 곧 source이므로 post_time을 기준으로 정점을 내림차순 정렬한다.
내림차순 정렬한 결과가 위상정렬의 결과다.
post_time 배열은 정점 v에서 출발하여 이동가능한 경로를 모두 탐색한 후 v로 되돌아왔을 때의 타임스탬프를 기록하는 용도다. post_time[v] 는 v에서 더 이상 이동가능한 경로가 없을 때 갱신한다. (위 설명에서 삭제와 같은 기능)
위 그래프의 경우 post_time이 가장 먼저 기록되는 순서로 정렬할 때 2 -> 1 -> 3 -> 4 가 될 것이다. (정점 2가 sink다.) 이를 내림차순으로 정렬하면 4 -> 3 -> 1 -> 2 가 되므로 위상정렬한 결과는 4 -> 3 -> 1 -> 2 가 된다.
출처
