위상 정렬 알고리즘 (Topology Sort)
위상 정렬이란 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스리지 않도록 순서대로 나열하는 것이다.
ex> 선수 과목을 고려한 학습 순서 결정 (우선순위)
선수 과목구조란 여러 수강 과목이 존재하는 경우 "c언어 과목을 들어야 알고리즘 강의를 수강할 수 있다"
라는 규칙을 지켜서 수강 신청을 하는 것을 말한다.
즉 어떤 그래프를 위상 정렬하면 그 결과로 정점들을 원소로 가지는 위상적 순서대로 정렬된 배열이 된다.
진입 차수 : 특정 노드로 들어오는 간선의 수
진출 차수 : 특정 노드에서 나가는 간선의 수
큐를 이용한 위상 정렬 알고리즘
파이썬을 통해서 위상정렬을 구현할 경우 큐를 활용한다.
위상 정렬 알고리즘의 규칙은 아래와 같다.
1. 모든 정점을 방문하기 전에 큐가 비는 상황이 발생하면 사이클이 존재한다.
- 위의 경우에는 위상 정렬 알고리즘을 사용할 수 없으며 탐색을 종료해야 한다.
2. 큐에서 마지막 원소를 꺼낸 후 확인한 순서가 위상 정렬의 결과가 된다.
- 위상 정렬 알고리즘을 수행한 결과는 원소를 차례대로 꺼낸 순서가 된다.
위상 정렬 알고리즘의 구현은 아래의 규칙을 반복한다.
1. 진입차수가 0인 모든 노드를 큐에 넣는다.
2. 큐가 빌 때까지 아래 과정을 반복한다.
- 새롭게 진입차수가 0이 된 노드를 큐에 넣음
- 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
3. 각 노드가 큐에 들어온 순서가 위상 정렬울 수행한 결과로 출력
정점과 진입차수를 저장한 그래프를 만들었을 경우 위와 같은 구조가 된다.
여기서 그래프를 통해서 진입 차수가 0인 정점 1을 우선적으로 큐에 삽입한다.
정점 1에 연결된 간선을 모두 제거한 후 진입 차수가 0이 된 2를 큐에 삽입한다.
정점 2에 연결된 간선을 제거한 후에 진입차수가 0이 된 정점 3을 큐에 삽입한다.
위의 과정을 반복했을 때, 모든 정점의 진입차수가 0이 된다.
방문하지 않은 노드가 없으므로, 사이클이 없는 방향 그래프이며 탐색을 완료한 것으로 한다.
노드를 순서대로 꺼낸 결과가 위상 정렬 알고리즘 수행 결과이므로
1, 2, 3, 4, 5를 순서대로 출력한다.
위의 모든 과정을 코드로 구현하면 아래와 같다.
import sys
input = sys.stdin.readline
import heapq
n,m = map(int,input().split())
indegree = [0] * (n+1)
graph = [[] for _ in range(0,n+1)]
for i in range(m):
a, b= map(int,input().split())
graph[a].append(b)
indegree[b] +=1
def topology_sort():
result = []
heap = []
# 초기 세팅 -> 진입차수가 0인 값 추가
for i in range(1,n+1):
if indegree[i] == 0:
heapq.heappush(heap,i)
while heap:
current = heapq.heappop(heap)
result.append(current)
for i in graph[current]:
# current로 부터 나가는 간선 제거
indegree[i]-=1
# 간선이 0이 되었다면 다시 추가
if indegree[i]==0:
heapq.heappush(heap,i)
for i in result:
print(i,end=" ")
topology_sort()