Pseudo Code
Coddy의 위상 정렬 - 그래프 알고리즘 코스 레슨 — 9개 중 4번째.
topologicalSort(n, edges):
build directed adjacency; compute indeg[v] for all v
order = []
repeat n times:
pick = smallest v with indeg[v] == 0 (none left -> stop)
mark pick as used (indeg[pick] = -1)
order.add(pick)
for nb in adj[pick]:
indeg[nb] -= 1
return order- indeg[v]는 들어오는 간선의 수를 셉니다. 오직
u -> v간선만이indeg[v]에 더해집니다. - 정점
0..n-1을 탐색하고 진입 차수가 0인 첫 번째 정점을 선택하는 것은 매 단계에서 가장 작은 선택지를 제공하므로, 순서가 결정론적(deterministic)입니다. indeg[pick] = -1로 설정하는 것은 정점이 이미 배치되었음을 표시하는 간단한 방법입니다.
직접 해보기
이 레슨에는 코드 챌린지가 없습니다.
실력 점검이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.
위상 정렬 - 그래프 알고리즘의 모든 레슨
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity