위상정렬

개요

수많은 정렬 알고리즘 중 위상정렬은 어떤 알고리즘인 걸까?

 

위상정렬이란?

모든 조건이 만족될 수 있도록 정해져 있는 순서를 일직선으로 정렬시키는 것이 위상정렬이다.

즉, 이미 정해져 있는 순서의 조건에 맞춰서 정점들을 일직선으로 정렬시키는 것이다.

 

따라서 위상정렬은 항상 시작점이 존재한다.

위상정렬을 할 수 없는 몇 가지 상황이 있다.

 

1. 시작점이 정해져 있지 않다면 위상정렬을 할 수 없다.

2. 그래프에 사이클이 있다면 위상정렬을 할 수 없다. (사이클이 있으면 명확한 시작 지점이 없으니까)

 

위상정렬의 흐름

정렬이 이루어지는 흐름에 대해 이야기하기 전에

"진입 차수"라는 용어를 설명하고 넘어가겠다.

 

진입 차수란?

-> 해당 정점으로 들어올 수 있는 길인 간선이 몇 개 존재하는지가 진입 차수이다.

 

이제부터 흐름에 대해 말하고자 한다.

 

1. 진입 차수가 0인 정점을 큐에 삽입한다.

 

2. 큐에서 원소를 꺼내 그 원소와 연결된 모든 간선을 제거한다.

 

3. 간선을 제거한 이후에 진입 차수가 0이 된 정점을 큐에 삽입한다.

 

4. While q 동안 2~3번을 반복한다. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이다.

 

5. 모든 원소를 방문했다면 큐에서 꺼냈던 순서가 곧 정렬되어지는 순서이다.

 

위상정렬의 흐름을 구현한 코드

from collections import deque

graph = graph
indegree = indegree

def topology():
    q = deque()
    sorted_arr = []
    
    for i in range(1, len(indegree)):		# 1
        if indegree[i] == 0:
            q.append(i)
    
    while q:
        now = q.popleft()					# 2
        sorted_arr.append(now)
        
        for i in graph[now]:				# 2
            indegree[i] -= 1
            if indegree[i] == 0:			# 3
                q.append(i)					# 3