자료구조와 알고리즘 - 위상정렬(Topological Sorting)

 

---

 

1. 위상정렬의 정의

 위상정렬은 일의 순서를 정하는 방법으로, 어떤 일들이 다른 일들보다 먼저 끝나야 할 때 사용됩니다. 예를 들어, 요리를 할 때 재료를 준비하고 나서 요리를 시작하는 것처럼, 순서를 지켜야 하는 작업들을 올바르게 나열하는 것입니다. 이는 주로 작업 스케줄링, 의존성 해결 등에서 사용됩니다.

 

 예를 들어, 주어진 그래프는 대학에서 학위를 취득하기 위해 수강해야 하는 과목들의 순서를 나타내고 있습니다. 각 과목은 선행 과목을 요구하며, 마지막에는 졸업시험을 치러야 합니다.

 

 그러면 이와 같이, 각 수강 순서는 선행 과목을 이수한 후에 후행 과목을 수강하는 형태로 나열됩니다. 이를 위상정렬이라고 합니다. 위상정렬의 결과는 여러가지가 될 수 있습니다.

 

2. 위상정렬의 원리

- 순환하지 않는 방향 그래프만 해당 알고리즘이 가능합니다.

- DFS, BFS 둘다 가능합니다. 이 예시는  BFS를 설명합니다.

- 진입 차수: 그래프의 점(vertext)에 들어오는 수

 

 

1) 설명

 

 

큐에서 pop된 순서가 위상정렬의 결과가 됩니다. 시간 복잡도는 V(점) 마다 E(간선)을 순회하므로 O(V+E)입니다.

 

2) 코드

from collections import deque
def topological_sort(graph,vertex):
    entries = [0] * vertex
    for i in range(vertex):
        for v in graph[i]:
            entries[v] += 1
            
    q = deque()
    for i in range(vertex):
        if not entries[i]:
            q.append(i)
            
    result = []
    while q:
        node = q.popleft()
        result.append(node)
        for next_node in graph[node]:
            entries[next_node] -= 1
            if not entries[next_node]:
                q.append(next_node)
    return result

g = {
    0: [1,2],
    1: [5],
    2: [3,4],
    3: [5],
    4: [5],
    5: []
}

answer = topological_sort(g,6)
print(answer)

 

3) 관련 문제

https://leetcode.com/problems/course-schedule-ii/description

 

 

https://www.acmicpc.net/problem/2252