卡恩演算法 | 會動的演算法

符號表示

資料
節點的入分支度deg
排序完成的順序order

初始化入分支度
計算各節點的入分支度。
排序
將入分支度為 0 的節點插入佇列。que.enqueue(v)
從佇列中取出入分支度為 0 的節點,並固定其順序。u ← que.dequeue()
order[u] ← t++
將相鄰節點的入分支度減 1。deg[v]--
已排序完成的節點群組。order 已確定的節點
輸出排序結果
輸出節點的順序。

演算法動畫

初始化入分支度
卡恩演算法 | 初始化入分支度

排序
卡恩演算法 | 排序

輸出排序結果
卡恩演算法 | 輸出排序結果