[Python] 그래프 - 위상 정렬 알고리즘

위상 정렬

• 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘
• 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것

위상 정렬을 수행하게 되는 예시: 선수과목을 고려한 학습 순서 결정

 

진입 차수 / 진출 차수

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

 

위상 정렬 알고리즘

큐를 이용한 동작 과정이다.

1. 진입차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
   i) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
   ii) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

이때 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다. 사이클이 존재하는 경우 사이클에 포함되어 있는 원소 중에서 어떠한 원소도 큐에 들어가지 못하기 때문이다. (진입차수가 0이 될 수 없음) 다만, 기본적으로 위상 정렬 문제에서는 사이클이 발생하지 않는다고 명시하는 경우가 더 많으므로 이 경우는 고려하지 않은 풀이이다.

따라서 다음 위상 정렬 알고리즘은 DAG(순환하지 않는 방향 그래프)에서 적용 가능하다.

 

from collections import deque

v, e = map(int, input().split()) # 노드의 간선의 개수

graph = [[] for _ in range(v+1)] # 각 노드에 연결된 간선 정보를 담는 리스트
indegree = [0] * (v+1)  # 모든 노드에 대한 진입차수는 0으로 초기화

for _ in range(e):
    a, b = map(int, input().split()) # a에서 b로 이동 가능
    graph[a].append(b)
    indegree[b] += 1


def topology_sort():
    queue = deque()

    # 진입차수가 0인 노드를 큐에 삽입
    for i in range(1, v+1):
        if indegree[i] == 0:
            queue.append(i)

    res = [] # 위상 정렬 수행 결과

    while queue:
        vertex = queue.popleft()
        res.append(vertex)

        for i in graph[vertex]:
            indegree[i] -= 1
            if indegree[i] == 0:
                queue.append(i)

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

topology_sort()

결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다.