勵志

勵志人生知識庫

kahn算法

Kahn算法是一種用於對有向無環圖(DAG)進行拓撲排序的算法。其基本思想是不斷移除入度為0的頂點,直到所有頂點都被訪問完畢。如果圖中存在環,則拓撲排序無法完成。

Kahn算法的實現步驟如下:

初始化一個空的結果列表和一個空的佇列。

遍歷圖中的所有頂點,計算每個頂點的入度(指向該頂點的邊的數量),並將入度為0的頂點加入佇列。

當佇列不為空時,從佇列中取出一個頂點v,並將其添加到結果列表中。

遍歷頂點v的所有鄰居頂點w,並將頂點w的入度減1。

如果頂點w的入度變為0,將頂點w加入佇列。

如果結果列表的長度等於圖中頂點的數量,說明圖中沒有環,返回結果列表作為拓撲排序的結果;否則,圖中存在環,拓撲排序無法完成。