위상 정렬(topological sort)

위상 정렬이란 뱡향있는 그래프 내 정점들의 선형 순서를 이용하여 정렬하는 것을 뜻한다. 위상정렬이 가능하려면 그래프는 DAG(Directed Acyclic Graph)여야 한다.

소스 & 싱크

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

• 소스(source) - 안으로 들어오는 간선이 없는 정점

• 싱크(sink) - 밖으로 나가는 간선이 없는 정점

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

위상정렬 과정

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

1. 싱크를 찾는다.

2. 결과 리스트에 삽입한다.

3. 찾은 싱크와 싱크로 들어오는 간선을 그래프에서 삭제한다.

4. 그래프가 빌 때 까지 1 ~ 3 을 반복한다.

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

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

1. 임의의 정점에서 출발하여 더 이상 다른 정점으로 이동할 수 없는 정점까지 간선을 타고 이동한다.

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

시간복잡도

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

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를 사용한다.

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을 이용하여 아래의 그래프를 위상 정렬한다.

과정은 아래와 같다.

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 가 된다.

출처

• 코세라 알고리즘 강의