我有一個向無環圖其中每個節點代表一個任務，每一個有向邊A -> B意味着task A前應task B開始識別冗餘依賴於圖表
一個簡單的例子可能是這樣進行：
所以這實際上是一個工作流程。在該圖中，邊緣A -> B被認爲是冗餘的，因爲任務B需要首先完成任務C，並且任務C需要首先完成任務A. （更不用說另一條路徑A -> D -> E -> B，這使得不需要A -> B）
問題是：我想確定（說，只是輸出）圖上的所有冗餘依賴（邊）。我的朋友和我有這樣一個想法：迭代遍歷圖上的所有邊，並且對於每條邊說X -> Y，將其刪除並檢查從X到Y（例如，運行DFS/BFS）的連接性，如果仍然存在一個路徑（除了被刪除的路徑），那麼邊緣X -> Y是多餘的，可以被物理刪除，否則就把它放回去。在這種情況下，最壞情況下的複雜度可能是O(n^2)（DFS/BFS每次通過幾乎所有邊），其中n代表圖上邊的數量。
我不知道這是否有任何優化？
你有沒有聽說過Transitive reduction？ From Wikipedia
有向圖的傳遞式約化是一個儘可能少的邊，與給定圖具有相同可達性關係的圖。等價地，給定圖及其傳遞約化應該具有彼此相同的傳遞閉包，並且其傳遞約化在所有具有此屬性的圖中應該儘可能少的邊。傳遞約化是由Aho，Garey & Ullman（1972）提出的，他們提供了構建它們的計算複雜度的嚴格界限。
您可以從Transitive Reduction獲取詳細信息。如果有向非循環圖中的頂點數量n和邊的數量m，則可以在時間O(nm)中找到傳遞減少量。
使用帶堆棧的DFS進行拓撲排序可以產生線性時間結果，可以通過從頂點開始，標記訪問，然後遞歸執行拓撲排序到所有未訪問的相鄰邊，一旦所有這些都是探索推頂點堆棧。
然後只需從堆棧打印，它會在線性時間內生成結果，更多可以參考以下鏈接中說明的算法。
拓撲排序不是我想要的東西，它只能產生表示與圖形兼容的順序的序列。在這個問題背後的實際情況下，該圖中的任務C和任務D可以在2個線程中同時運行，這種拓撲排序不能真正體現。 –
好吧，如果你可以用拓撲排序來繪製依賴圖，我不會很難找到相同級別的依賴關係的節點嗎？所以現有的alog可以進一步修改來解決這個問題。 – Techfist
這正是我想要的。我注意到維基沒有提供標準的實現或僞代碼。猜猜我最好參考那些論文。 –