사이클이 없는 방향 그래프에서, 모든 노드에 대해 방향을 거스르지 않으면서, 방향이 특정된 노드 순서대로 나열하는데 활용하는 알고리즘
위상정렬 알고리즘은 DFS를 이용하거나, Queue를 이용하여 구현할 수 있다.
사용 graph는 사이클이 없는 방향그래프(DAG)이고, 진입차수가 0인 노드가 존재해야 적용할 수 있다.
※ 큐에 들어온 노드의 순서가 위상정렬의 결과이다.
최초 진입차수가 0인 노드1을 Queue에 넣는다.
이때 노드1에 인접해있는 노드의 진입차수를 1만큼 뺀다.
위에서 갱신한 진입차수를 참조하여, 새롭게 진입차수가 0이된 노드들을 다시 Queue에 넣는다.
다시 큐에서 노드들을 추출하면서, 간선을 제거하고 다시 Queue에서 노드들을 추출하는 과정을 Queue가 빌때까지 반복 수행한다.
※위상정렬의 특징을 유의해가며 알고리즘을 구현해본다.
from collections import deque
import sys
#노드 개수와 간선 개수
v, e = map(int, sys.stdin.readline().split())
#진입차수배열(노드는 1부터 시작)
indegree = [0] * (v+1)
#graph 간선정보
graph = [[] * (v+1) for _ in range(v+1)]
#방향그래프 간선정보(각 노드별 인접노드를 입력받는다)
for _ in range(e):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b) #a > b 통로
indegree[b] = indegree[b] + 1
#위상정렬 수행
def topologySort():
result = []
q = deque()
# 최초 queue에 진입차수가 0인 노드를 삽입
for i in range(1, v+1):
if indegree[i] == 0:
q.append(i)
while q:
now = q.popleft()
result.append(now)
#인접노드
for i in graph[now]:
indegree[i] = indegree[i] - 1
#새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if indegree[i] == 0:
q.append(i)
for i in result:
print(i,end=' ')#결과출력
topologySort()
이코테 2021 - 위상정렬
https://www.youtube.com/watch?v=aOhhNFTIeFI&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=8