[Algorithm/Python] 위상 정렬(Topology Sort)란?

들어가며

본 포스팅에서는 위상 정렬에 대해 소개합니다.

---

📌 위상 정렬이란?

위상 정렬(Topology Sort)이란 방향 그래프의 모든 노드를 방향성을 모두 지키며 순서대로 나열하는 것을 의미합니다. 
 
 
특정한 노드로 들어오는 간선의 개수를 진입차수라 합니다.
1️⃣ 진입차수가 0인 노드를 큐에 담습니다.
2️⃣ 큐가 비어있을 때까지 다음의 과정을 반복합니다.
- 1 ) 큐에 담긴 노드를 꺼내어 해당 노드에서 출발하는 모든 간선을 그래프에서 제거합니다.
- 2 ) 진입차수가 0인 노드를 큐에 담습니다.
 
모든 원소를 방문하지 않았는데 큐가 비었다는 것은 사이클이 발생했다는 것을 의미합니다. 
큐에 담기는 노드가 2개 이상인 경우, 위상 정렬된 후의 결과가 여러 개일 수 있습니다.
 
1. 진입차수가 0인 노드 1을 큐에 담습니다.

노드	1	2	3	4	5	6	7
진입차수	0	1	1	2	1	2	1

큐

노드 1

 
2. 큐에 담긴 노드 1을 꺼내어, 해당 노드에서 출발하는 간선을 모두 그래프에서 제거합니다. 그 후 진입차수가 0인 노드를 큐에 담습니다.

노드	1	2	3	4	5	6	7
진입차수	0	0	1	2	0	2	1

큐

노드 2

노드 5

 
3. 큐에 담긴 노드 2를 꺼내어, 해당 노드에서 출발하는 간선을 모두 그래프에서 제거합니다. 그 후 진입차수가 0인 노드를 큐에 담습니다.

노드	1	2	3	4	5	6	7
진입차수	0	0	0	2	0	2	1

큐

노드 5

노드 3

 
4. 큐에 담긴 노드 5를 꺼내어, 해당 노드에서 출발하는 간선을 모두 그래프에서 제거합니다. 그 후 진입차수가 0인 노드를 큐에 담습니다.

노드	1	2	3	4	5	6	7
진입차수	0	0	0	2	0	0	1

큐

노드 3

노드 6

 
5. 큐에 담긴 노드 3를 꺼내어, 해당 노드에서 출발하는 간선을 모두 그래프에서 제거합니다. 그 후 진입차수가 0인 노드가 존재하지 않으므로 넘어갑니다.

노드	1	2	3	4	5	6	7
진입차수	0	0	0	1	0	0	1

큐

노드 6

 
6. 큐에 담긴 노드 6를 꺼내어, 해당 노드에서 출발하는 간선을 모두 그래프에서 제거합니다. 그 후 진입차수가 0인 노드를 큐에 담습니다.

노드	1	2	3	4	5	6	7
진입차수	0	0	0	0	0	0	1

큐

노드 4

 
7. 큐에 담긴 노드 4를 꺼내어, 해당 노드에서 출발하는 간선을 모두 그래프에서 제거합니다. 그 후 진입차수가 0인 노드를 큐에 담습니다.

노드	1	2	3	4	5	6	7
진입차수	0	0	0	0	0	0	0

큐

노드 7

 
8. 큐에 담긴 노드 7을 꺼내고 출발하는 간선과 전입차수가 0인 노드가 존재하지 않습니다. 이렇게 큐에서 꺼내어진 노드 순서대로 출력하여 위상 정렬을 마칩니다.
 

✅[ CODE ]

"""
< 위상 정렬>
"""
from collections import deque

v, e = map(int, input().split())

indegree = [0] * (v + 1)
graph = [[] for _ in range(v + 1)]

for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1


def topology_sort():
    result = []
    q = deque()

    for i in range(1, v + 1):
        if indegree[i] == 0:
            q.append(i)

    while q:
        now = q.popleft()
        result.append(now)
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)

    for i in result:
        print(i, end=" ")


topology_sort()

 

☑️ 시간 복잡도

모든 노드를 확인하며 해당 노드와 연결된 간선을 제거해야 하므로 시간 복잡도 $O(V + E)$가 됩니다.

---

포스팅 내용에 오류 및 문제가 있는 경우, 댓글로 남겨주시면 감사하겠습니다.
파파파파파이이팅
 
출처) 이것이 코딩 테스트다 with Python