什麼是最有效的方式來保持增長的拓撲排序樹非循環？

Question

我知道至少有兩種方法。

一種方法是每次將邊添加到非循環樹時，遍歷必需的頂點。

缺點是隨着樹變大，遍歷過程需要越來越多的時間。

另一種方式是被動地檢查添加的邊是否創建了無限循環。

Answer 1

我不確定拓撲排序是在哪裏進行的，所以這裏只是您在哪裏創建節點之間的鏈接的答案。

開始時假設您只有一組斷開連接的節點。在添加鏈接時，通過鏈接將節點製作成樹。如果您創建了一個鏈接來添加兩個先前分離的樹，則不會創建一個循環。如果在已經在同一棵樹中的兩個節點之間添加鏈接，則創建一個循環。因此，您可以通過檢查您要鏈接的兩個節點是否已經在同一棵樹中來檢查週期。

這是union-find，在http://en.wikipedia.org/wiki/Disjoint-set_data_structure中描述了這樣做的有效方法。

Answer 2

我對你提到的拓撲排序感到困惑，因爲如果你做一個拓撲排序，你可以免費獲得循環檢測，這可以在諸如http://en.wikipedia.org/wiki/Topological_sort之類的地方進行解釋。您還將獲得週期檢測http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29#Algorithms。

想想這個，我想知道你是否試圖在有向圖中進行在線循環檢測。我想我曾經在Unix中看到過一些代碼來檢測用戶代碼產生的死鎖 - 它是迭代的，並且依賴於進程只能等待一個事件的事實。我認爲這對應於你的「遍歷必要頂點」。

似乎有一些方案依賴於維護拓撲排序順序。然後，如果您添加與訂單一致的鏈接，則表示您尚未引入週期。問題在於，如果添加與訂單不一致的鏈接，則必須檢查週期並維護訂單。在http://homepages.ecs.vuw.ac.nz/~djp/files/tr0703.pdf

中描述了三種這樣的算法