[알고리즘] 위상 정렬 파이썬 구현

자료 출처: https://youtu.be/aOhhNFTIeFI

1. 위상 정렬

사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 알고리즘

• 진입 차수(Indegree): 특정 노드로 들어오는 간선의 개수
• 진출 차수(Outdegree): 특정 노드에서 나가는 간선의 개수

2. 큐를 이용하는 위상 정렬 알고리즘

• 진입 차수가 0인 모든 노드를 큐에 담는다.
• 큐가 빌 때까지 다음을 반복한다:
  • 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거함
  • 새롭게 진입 차수가 0이 된 노드를 큐에 넣음
• 결과적으로는, 각 노드가 큐에 들어온 순서와 위상 정렬을 수행한 결과가 동일하다.
• 위상 정렬에는 여러 가지 답이 존재할 수 있다.
• 모든 원소를 방문하기 전에 큐가 빈다면? 사이클이 존재한다는 뜻: 사이클이 포함된 경우에는 진입차수가 0이 아니기 때문에 큐에 들어가지 못함
• 스택, DFS를 이용하여 위상 정렬을 수행할 수도 있다.

3. 파이썬 구현

from collections import deque

# 노드 개수와 간선 개수를 입력받음
v, e = map(int, input().split())

# 모든 노드에 대한 진입 차수를 0으로 초기화한다. 노드이기 때문에 1부터 세서 (v + 1)개
indegree = [0] * (v + 1)

# 각 노드에 연결된 간선의 정보를 담기 위한 연결 리스트를 초기화한다.
graph = [[] for _ in range(v + 1)]

for _ in range(e): # 모든 간선에 대하여 정보를 입력받는다.
    a, b = map(int, input().split())
    graph[a].append(b) # 정점 a에서 b로 이동 가능
    indgree[b] += 1 # b의 진입차수를 1 증가시킴
    
def topology_sort(): # 위상 정렬 함수
    result = []
    q = deque()
    
    for i in range(1, v + 1): # 모든 노드에 대하여, 처음 시작 시 진입 차수가 0인 노드를 큐에 삽입함
        if indegree[i] == 0:
            q.append(i)
            
    while q:
    
        # 현재의 노드
        now = q.popleft()
        result.append(now)
        
        # 현재 노드의 인접 노드들에 대하여, 인접 노드들의 진입 차수에서 1을 빼주기
        for i in graph[now]:
            indegree[i] -= 1
            
            # 새롭게 진입 차수가 0이 되는 노드를 큐에 삽입함
            if indegree[i] == 0:
                q.append(i)
                
    for i in result:
        print(i, end = " ")

topology_sort()

4. 위상 정렬의 성능 분석

차례대로 모든 노드를 확인하며 각 노드에서 나가는 간선을 차례대로 제거하기 때문에 O(V + E)의 시간 복잡도를 갖는다.