Pseudo Code
Coddyの「トポロジカルソート - グラフアルゴリズム」コースのレッスン 4/9。
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 である最初の頂点を選択することで、各ステップで最小の選択肢が得られるため、順序は一意に決まります。 indeg[pick] = -1と設定することは、頂点がすでに配置済みであることをマークする簡単な方法です。
自分で試してみよう
このレッスンにはコードチャレンジは含まれていません。
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
トポロジカルソート - グラフアルゴリズムのすべてのレッスン
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity