위상정렬 (Topological Sotring)

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

특징

- 사이클이 없는 방향 그래프(DAG)에 대해서만 수행 가능
- 위상 정렬에는 여러 가지 답이 존재할 수 있다.
- 모든 원소를 방문하기 전에 큐가 빈다면, 사이클이 존재한다고 판단할 수 있음
- 보통 큐'로 구현하지만 스택을 이용한 DFS로도 구현할 수 있다.

원리

• 진입 차수가 0인 노드를 큐에 넣음
• 큐가 빌 때까지 다음 과정을 반복
  1. 큐에서 원소를 꺼내 해당 노드의 진출 차수들을 그래프에서 제거
  2. 새롭게 진입 차수가 0이 된 노드를 큐에 삽입>

진입차수 ( In-Degree ) : 특정 노드로 들어오는 간선의 수
진출차수 ( Out-Degree ) : 특정 노드에서 나가는 간선의 수

예제

from collections import deque

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

# 모든 노드에 대한 진입차수 0으로 초기화
indegree = [0] * (v + 1)

# 인접 리스트 생성
graph = [ [] for _ in range(v + 1) ]

# 간선 정보에 따라 도착 노드에 해당되면 indegree 리스트에서 해당 노드 진입차수 1 증가
for _ in range(e):
  s, e = map(int, input().split()
  graph[a].append(b)
  indegree[b] += 1
  
# 위상 정렬 함수
def topology_sort():
  result = []
  q = deque()
  
  for i in range(1, v + 1):
# 진입 차수가 0인 노드를 큐에 넣음
    if indegree[i] == 0:
      q.append(i)
      
# 큐에 노드가 존재하면, 꺼내서 인접 노드를 확인
   while q:
     now = q.popleft()
     result.append(now)
     
# 인접 노드를 방문했다면 진입차수 1 감소
     for g in graph[now]:
       indegree[g] -= 1
# 만약 이번 방문으로 진입차수가 0이 된 인접 노드가 있다면, 큐에 추가
       if indegree[g] == 0:
       	q.append(g)

for res in result:
  print(res, end=' ')
  
topology_sort()

# sample input
# 7 8
# 1 2
# 1 5
# 2 3
# 2 6
# 3 4
# 4 7
# 5 6
# 6 4

예제, 썸네일, 본문 출처 , 출처