다양한 그래프 알고리즘 (3) : 위상 정렬

위상 정렬 (Topology Sort)

위상 정렬은 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 이다.

쉽게 말하면, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다.

예를 들어 '알고리즘'을 배우기 위해 '자료구조'를 먼저 배워야 하고,
'자료구조'를 배우기 위해 '프로그래밍 언어'를 먼저 배워야 한다.

'프로그래밍 언어' ➡️ '자료구조' ➡️ '알고리즘'

여기서 ➡️를 진입차수 라고 한다.
진입차수란 한 노드로 들어오는 간선의 개수를 의미한다.
진출차수란 한 노드에서 나가는 간선의 개수를 의미한다.

아이디어 :

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

• 위상 정렬을 수행할 그래프는 사이클이 없는 방향 그래프(DAG, Direct Acyclic Graph)여야 한다.

• 위상 정렬에서는 여러 가지 답이 존재할 수 있다.
  (한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면)

• 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단

python을 이용한 위상정렬 :

from collections import deque

def topologySort() :
    result = []
    q = deque()
    for i in range(1, v+1) :
        if indegree[i] == 0 :
            q.append(i)
    while q :
        node = q.popleft()
        result.append(node)
        # pop한 node와 연결된 노드의 indegree -1
        for i in graph[node] :
            indegree[i] -= 1
            if indegree[i] == 0 :
                q.append(i)
    for i in result :
        print(i, end=' -> ')

v, e = map(int, input().split())
indegree = [0] * (v + 1)
graph = [[] for i in range(0, v+1)]

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

topologySort()