# 위상 정렬(topological sort)

위상 정렬이란 뱡향있는 그래프 내 정점들의 선형 순서를 이용하여 정렬하는 것을 뜻한다. 위상정렬이 가능하려면 그래프는 [DAG(Directed Acyclic Graph)](https://kde6260.gitbook.io/dev/directed-graph#dag-directed-acyclic-graph)여야 한다. 

### 소스 & 싱크

위상 정렬에서는 정점을 2가지로 분류 한다.

* **소스(source)** - 안으로 들어오는 간선이 없는 정점
* **싱크(sink)** - 밖으로 나가는 간선이 없는 정점

![](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-LxaRKKXMgrFcF6GHglF%2F-LxaVvLPNHmlDXWC1UQG%2Fdag.png?alt=media\&token=8acba160-53d5-4582-9e67-f1c29f455547)

위 DAG에서 소스는 정점 `A`와 `G`이며 싱크는 정점 `F`다. 

### 위상정렬 과정

위상정렬 과정은 아래와 같다.

1. **싱크를 찾는다.**
2. **결과 리스트에 삽입한다.**
3. **찾은 싱크와 싱크로 들어오는 간선을 그래프에서 삭제한다.**
4. **그래프가 빌 때 까지 1 \~ 3 을 반복한다.**

![](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-LxaYm-bWHrAvocZTxwX%2F-LxaZE06w_9s-0iiZrAs%2Fdirected_graph.png?alt=media\&token=0c9bdb64-177b-4f27-9e87-2e7102838320)

위 그림의 경우 `5 -> 4 -> 2 -> 3 -> 1` 순서로 정점이 그래프에서 삭제되므로 위상정렬의 결과는

`1 -> 3 -> 2 -> 4 -> 5` 가 될 것이다. 그렇다면 그래프에서 어떻게 싱크를 찾을 수 있을까?

1. 임의의 정점에서 출발하여 더 이상 다른 정점으로 이동할 수 없는 정점까지 간선을 타고 이동한다.
2. 정점을 매번 이동할 때는 해당 정점이 이전에 방문했던 정점으로 향하는 간선을 가지고 있지 않은지 확인한다. 즉, 그래프에 사이클이 있는지 확인한다. 사이클이 있다면 정렬을 할 수 없기 때문이다.

### 시간복잡도

위상정렬의 시간복잡도는 얼마나 될까? 아래와 같은 DAG가 있다고 가정하자.

![](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-LxaZrmOZgaw0OEtfetC%2F-LxabSnsrPK3uR-XcpvG%2Flinear_dag.png?alt=media\&token=af0522c7-483a-413b-b123-a652f804e35c)

1. `A0`에서 출발하여 정점 `A3`까지 이동 후 `A3`을 삭제한다.
2. `A0`에서 출발하여 정점 `A2`까지 이동 후 `A2`를 삭제한다.
3. `A0`에서 출발하여 정점 `A1`까지 이동 후 `A1`을 삭제한다.
4. `A0`을 삭제한다.

싱크를 찾아서 삭제하는 과정이 1번 발생할 때마다 그래프 내 모든 정점을 탐색하므로 이 때의 시간복잡도는 `O(|V|)`이다. 싱크를 찾아서 삭제하는 과정은 정점의 갯수만큼 발생하므로 **시간복잡도는 `O(|V| * |V|) = O(|V| ^ 2)` 이다. 즉, 정점의 갯수의 제곱이 시간복잡도가 되는 것이다.**

그러나 그래프의 정점의 갯수가 매우 많다면 시간복잡도가 `O(|V|^2)`인 정렬은 매우 느린 알고리즘이 될 것이다. 따라서 그래프에서 싱크를 삭제하기 위해 매번 첫 정점에서부터 이동을 시작하지 않고, 삭제된 싱크 바로 이전의 정점으로 상태를 되돌리는 방법을 사용한다. 즉, DFS를 사용한다.

```python
def topological_sort():
    for i in range(n):
        if not post_time[i]:
            explore(i)

    sorted_result = sorted(post_time, key=lambda x: x[1], reverse=True)
    return [x[0] for x in sorted_result]


def explore(v):
    for adj_v in adjacent_list[v]:
        if not post_time[adj_v]:
            explore(adj_v)

    global post_time_cnt
    post_time_cnt += 1
    post_time[v] = (v + 1, post_time_cnt)


if __name__ == '__main__':
    n = 4  # 정점은 4개
    post_time = [None for _ in range(n)]
    post_time_cnt = 0
    adjacent_list = [  # 간선은 3개
        (1, 2),
        (3, 1),
        (4, 1),
    ]

    result = topological_sort()
    print(' '.join([str(e) for e in result]))


```

위 코드는 DFS와 post\_time을 이용하여 아래의 그래프를 위상 정렬한다.

![](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-Lxjlkt68UVZRABOC4I_%2F-LxkLQs5mvHdNz6Hr-Vc%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-01-04%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%208.37.41.png?alt=media\&token=61294a3e-a08c-4a45-927c-6341ef0935df)

 과정은 아래와 같다.

1. 그래프 전체를 DFS하면서 각 정점의 `post_time`을 기록한다. 
2. 가장 큰 `post_time`을 가진 정점이 곧 `source`이므로 `post_time`을 기준으로 정점을 내림차순 정렬한다.
3. 내림차순 정렬한 결과가 위상정렬의 결과다.

`post_time` 배열은 정점 `v`에서 출발하여 이동가능한 경로를 모두 탐색한 후 `v`로 되돌아왔을 때의 타임스탬프를 기록하는 용도다. `post_time[v]` 는 `v`에서 더 이상 이동가능한 경로가 없을 때 갱신한다. (위 설명에서 삭제와 같은 기능)

위 그래프의 경우 `post_time`이 가장 먼저 기록되는 순서로 정렬할 때 `2 -> 1 -> 3 -> 4` 가 될 것이다. (정점 `2`가 sink다.) 이를 내림차순으로 정렬하면 `4 -> 3 -> 1 -> 2` 가 되므로 위상정렬한 결과는 `4 -> 3 -> 1 -> 2` 가 된다.

출처

* [코세라 알고리즘 강의](https://www.coursera.org/learn/algorithms-on-graphs?specialization=data-structures-algorithms)