위상 정렬

calendar 2024-01-04

유향 그래프의 정점을 탐색 가능한 순서로 정렬하는 알고리즘이다.

  1. 유입 간선이 없는 정점들을 찾아 정렬된 리스트에 추가한다.
    1. 유입 간선이 없으므로 바로 탐색해도 무방한 정점들이다.
  2. 해당 정점들의 유출 간선들을 제거한다.
    1. 앞선 정점들을 방문한 상황에서는, 해당 간선들이 그 다음 탐색에 영향주지 않는다.
  3. 모든 정점을 정렬할 때 까지 1과 2를 반복한다.
    1. 불가하다면 그래프에 사이클이 존재하는 것이다.
[구현 예시]
from collections import defaultdict, deque

indegree = defaultdict(int) 
for v, neighbors in G.items(): 
	for neighbor in neighbors:
		indegree[neighbor] += 1

Q = deque() 
for v in G.keys():
	if indegree[v] == 0:
		Q.append(v)

result = []
while Q:
	v = Q.popleft()
	result.append(v)
	
	for neighbor in G[v]:
		indegree[neighbor] -= 1
		if indegree[neighbor] == 0: 
			Q.append(neighbor)

refs