如何忽略拓撲排序中的循環？

Question

我正在使用this library在JS中的圖上執行拓撲排序。問題是，在極少數情況下，圖形將包含循環。這些只是結構的一小部分，所以減少一些邊緣不會對最終結果產生相當大的影響。然而，算法出現時就會中斷。什麼是最有效的方式來更新它，所以如果有一個或兩個週期它不會崩潰？

Answer 1

根據Wikipedia：

甲拓撲順序是可能的，如果且僅當圖沒有向圈，即，如果它是一個有向非循環圖（DAG）。

因此，如果圖形包含循環，則無法找到有效的topsort。我想你使用的庫對輸入圖有一個要求是DAG。因此，該算法因該要求而中斷。

但是，如果您仍想找到一些topsort，您可以對圖進行以下修改之一： 1）構建圖的隨機生成樹。通過這種方式，您可以將圖形修改爲DAG，並且可以在新圖形上運行topsort算法。

2）找到圖的強連通組件（用Tarjan的強連通組件算法）。新圖形是DAG，因此您可以在其上運行topsort算法。

我建議你這兩個選項，因爲至少有幾個JavaScript庫有這些算法（對於1，你可以使用一個構建圖的最小生成樹的庫（MST））。最佳實施，兩種算法都具有線性複雜性。

此外，您可以運行自己修改的DFS算法，該算法會刪除它找到的每個圖形週期的單個邊沿。

Answer 2

使離開非循環圖的電弧數量最小化的問題稱爲feedback arc set。鏈接到的拓撲排序使用重複找到度0的頂點並將其移除的算法。 Eades-Lin-Smyth反饋弧集的啓發式算法並不遙遠，可以概括如下。如果存在0度的頂點v，則刪除它，在剩餘圖上進行遞歸，並將v加到訂單上。如果存在度數爲0的頂點v，則刪除它，在殘差圖上遞歸，並將v附加到該順序。否則，讓v有最大的出度減去入度，刪除所有的入弧，並繼續。