위상 정렬(Topology Sort)

정의:

• 방향(direction) graph의 모든 node를 "방향성에 거스르지 않도록 순서대로 나열하는 것"

특징:

• 정렬 알고리즘 중 하나
• 순서가 정해진 일련의 작업을 차례대로 수행해야 할 때 사용
  예시> 선수과목을 고려한 학습 순서 설정

위상 정렬 알고리즘:

1. 진입차수(indegree)가 0인 queue에 넣는다
2. queue가 빌 때까지 다음의 과정을 반복한다
   • 1. queue에서 원소를 꺼내 해당 노드에서 출발하는 edge를 graph에서 제거한다
   • 2. 새롭게 진입차수가 0이 된 node를 queue에 넣는다

source code 예시

# 이코테 p.296 위상 정렬 
from collections import deque

v, e = map(int, input().split())
indegree = [0] * (v + 1)

graph = [[] for i 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()

시간 복잡도