위상정렬(topological sort)

[위상정렬]

위상정렬에서의 위상(位相)은 사전적 의미로 어떤 사물이 다른 사물과의 관계 속에서 가지는 위치나 상태이다.

위상정렬은 영어로 topological sort인데 topological란 위상배치적인 이라는 뜻으로 구성요소간의 관계를 고려하여 배치한다는 뜻이다.

여기서 키워드는 관계이다. 노드 간의 관계(방향을 가진 간선)를 고려하여 방향성에 거스르지 않게 모든 노드를 나열하여 데이터를 정렬하는 것을 말한다.

 

 

[위상정렬 알고리즘]

방향 그래프에서 각 노드로 들어오는 간선의 수를 "진입 간선 수"라 할 때

1. 모든 노드별로 진입 간선 수를 저장한다.
2. 진입 간선 수가 0개인 노드를 queue에 넣는다.
3. queue가 비워진 상태일 때까지 다음을 실행한다.
   1. queue에서 dequeue하여  노드를 하나 꺼내고 그 이름을 c_node라 하자.
   2. 꺼낸 노드에서 출발하는 모든 간선을 제거한다.(c_node로부터 이어진 다른 각각의 노드들의 진입 간선 수에서 1을 빼준다.)
   3. 위 2번 과정을 실행 후 진입 간선 수가 0으로 변경된 노드들을 queue에 enqueue 한다. (이미 정렬된 요소 즉, result에 추가된 node는 다시 queue에 추가히지 않도록 주의한다.)

 

 

[위상정렬 알고리즘의 구현]

import sys
from collections import deque

fast_input = sys.stdin.readline
vertex, edge = map(int, fast_input().rstrip().split())
graph = [[] for _ in range(vertex + 1)]
num_of_entry = [0] * (vertex + 1)
for i in range(1, edge + 1):
    from_node, to_node = map(int, fast_input().rstrip().split())
    graph[from_node].append(to_node)
    num_of_entry[to_node] += 1


def topology_sort():
    result = []
    queue = deque()
    for i in range(1, vertex + 1):
        if num_of_entry[i] == 0:
            queue.append(i)
    while queue:
        current_node = queue.popleft()
        result.append(current_node)
        for i in graph[current_node]:
            num_of_entry[i] -= 1
            if num_of_entry[i] == 0:
                queue.append(i)
    for i in result:
        print(i, end=' ')


topology_sort()

 

[위상정렬의 시간복잡도]

모든 노드 순회하면서 각 노드에서 출발하는 간선을 순차적으로 제거해 나가기 때문에 모든 노드와 간선을 확인해야 하므로 노드의 수를 V, 간선의 수를 E라 할 때 O(V + E)의 시간 복잡도를 보인다.