사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열 하는 것을 의미한다.
예를 들어 아래와 같이 선수과목을 고려해 수강신청을 해야한다고 했을 때,
세 과목을 모두 듣기 위한 적절한 학습 순서는 자료구조 -> 알고리즘 -> 고급 알고리즘이 될것이다. 만약 자료구조를 수강한 뒤 고급 알고리즘을 먼저 듣게 되면, 이후 알고리즘을 신청할 때 방향성에 거르스게 되므로, 이는 적절치 못한 학습 순서가 된다.
또한 사이클이 있다면 시작 지점을 특정할 수가 없으므로 위상정렬은 꼭 사이클이 없는 방향 그래프(Direct Acyclic Graph)에서만 적용 가능하다.
위상정렬을 구현하기 위해서는 그래프에서 자주 나오는 개념인 진입차수와 진출차수를 알아야한다.
위상정렬 알고리즘은 큐를 이용한다.
- 진입차수가 0인 모든 노드를 큐에 넣는다.
- 큐가 빌 때까지 아래 과정을 반복한다.
- 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
- 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
결과적으로 큐에 들어온 노드들의 순서가 곧 위상 정렬을 수행한 결과 가 된다.
동작 예시는 해당 영상을 참고하면 도움이 될 것이니 꼭 한 번 시청하길 바란다 👍🏻
앞서 말했듯 위상정렬은 DAG에서만 수행이 가능하다.
위상정렬에서는 여러가지 답이 존재할 수 있다.
스택을 활용한 DFS를 이용해 위상 정렬을 수행할 수도 있다.
from collections import deque
v, e = map(int, input().strip().split())
indegree = [0] * (v + 1)
graph = [[] for i in range(v + 1)]
for _ in range(e):
a, b = map(int, input().strip().split())
graph[a].append(b)
indegree[b] += 1
def topological_sort():
result = []
q = deque()
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] -= 1
if indegree[i] == 0:
q.append(i)
for i in result:
print(i, end=" ")
topological_sort()