위상 정렬이라 번역되어 불리는 이 알고리즘은 방향성이 있는 그래프에서 노드들을 선행 관계에 따라 정렬하는 방법을 정의한다.
특징
DAG에만 적용 가능
- 방향성 그래프 중에서도 사이클이 없는 경우에만 사용이 가능하다. 사이클이 존재하면 정렬 할 수 없다.
- 왜?
위상 정렬은 진입 차수가 0인 노드부터 시작하여 단계적으로 순서를 정해나간다. 사이클이 있다고 하면, 모든 노드가 서로 연결 되어 있기 때문에 진입 차수가 0이 되는 노드가 존재 할 수 없다. A - B - C - A 같은 순환 구조에서는 어느 하나의 노드도 위상 정렬의 대상 노드로 지정 할 수 없다. 진입 차수 우선이 아닌 진출 차수를 고려해도 상황은 다르지 않다.
위상 정렬은 작업을 선후 관계에 따라 배치한다. 사이클이 있다면 어떤 작업이 먼저 시작되어야 하는지 결정 할 수 없다.
A를 먼저 처리하기 위해 B가 선행 작업 되어야 하고, B를 처리하려면 A를 먼저 해야한다. x같은 상황은 위상 정렬에서 시도 불가.
위상 정렬의 대표 알고리즘 Kahn's Algorithm은 사이클이 존재하는 경우 정렬을 완료 할 수 없다.
- 왜?
유일하지 않은 결과
- 특정 그래프에 대해 여러 가지 위상 정렬 결과가 나올 수 있다. 그래프에 구조에 따라 조금은 다르지만 대부분 해당한다.
- 왜?
노드 간 우선순위가 애매한 경우 : 위상 정렬은 선행 관계를 유지하면서 작업 순서를 정한다. 서로 독립적인 노드들 사이에서는 어떤 순서로 정렬하던 상관이 없다. 선행 관계로 강제되지 않았다면, 아무렇게나 배치 될 수 있다.
간선 수가 제한적인 경우 : 간선이 적어 노드 간의 의존성이 적다면, 정렬 순서에 더 많은 선택지를 고려 할 수 있다.
비유일성 예시를 좀 더 보자. A -> C <- B
C가 반드시 A와 B 이후에 위치해야 한다는 것이다. 그럼 A, B, C | B, A, C 둘 다 가능하다. - 결과가 유일한 경우?
- 그래프가 완전한 선형인 경우에만 가능하다.
- 왜?
from collections import deque
def topological_sort(graph):
# 진입 차수를 저장할 딕셔너리 생성
indegree = {node: 0 for node in graph}
for nodes in graph.values():
for node in nodes:
indegree[node] += 1
# 진입 차수가 0인 노드를 큐에 삽입
queue = deque([node for node in graph if indegree[node] == 0])
result = []
while queue:
current = queue.popleft()
result.append(current)
for neighbor in graph[current]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
# 그래프에 사이클이 있는 경우 처리
if len(result) != len(graph):
raise ValueError("Cycle detected in the graph!")
return result