如何使用拓撲排序在有向圖中找到一個循環？

我在程序中實現這個僞代碼，以檢查是否有向圖是非循環：如何使用拓撲排序在有向圖中找到一個循環？

L ← Empty list that will contain the sorted elements 
S ← Set of all nodes with no incoming edges 
while S is non-empty do 
    remove a node n from S 
    add n to tail of L 
    for each node m with an edge e from n to m do 
     remove edge e from the graph 
     if m has no other incoming edges then 
      insert m into S 
if graph has edges then 
    return error (graph has at least one cycle) 
else 
    return L (a topologically sorted order)

這個偉大的工程，但我也需要輸出的實際週期，如果圖不是無環的。是否可以在代碼中「執行」，還是需要完全改變我的算法？我試圖尋找解決方案，並且我找到了這個答案（Printing(not detecting) cycle with topological sort），但我無法理解如何實際執行此操作。有沒有人有一些僞碼可以幫助我？

來源

2014-10-27 user16655

您是否在圖表算法中閱讀過*彩圖*？一旦你有一個適當的DFS算法使用彩色地圖，檢測一個週期是微不足道的。如果你曾經沿着一條邊並遇到一個*灰色*頂點，你就找到了一個循環。既然你想打印週期中包含的頂點，你可以展開當前正在探索的頂點堆棧，直到你在堆棧中再次找到同樣有問題的灰色頂點。 – seh 2014-10-27 19:08:33

我還沒有讀到這個，但它似乎是一個更好的計劃。不過，我想使用我已經實現的解決方案，因爲我的整個程序（相當大的一個）取決於拓撲排序。如果我沒有得到它的工作，我會定義看你的建議:) – user16655 2014-10-27 19:22:49

我還不夠清楚：爲了排序拓撲，你運行深度優先行走（「DFW」，而不是DFS，因爲有不涉及搜索），並且如果*不*發現週期，則只發出*黑色*頂點。因此，DFW既能確保您的圖形是非循環的，又能同時進行拓撲排序。 DFW和拓撲排序不是相互排斥的;你根據DFW實現拓撲排序。 – seh 2014-10-27 19:25:34

首先，你要做的是有點問題，因爲可能有多個週期。理論上，圖中的每個節點都可以有一個自定義邊，然後會有n個週期。

但是，一個簡單的方法是抓住圖中的任何邊，然後對其進行迭代，直到回到相同的邊，並將其輸出爲循環。導致死點的邊應該被移除，並且找到的任何週期也應該從圖中移除所有的週期邊。繼續這樣做直到圖形沒有更多的邊，這應該輸出圖中的所有周期，儘管沒有特定的順序或優化，並且如果以特定順序執行，可能會錯過一些週期。

來源

2014-10-27 15:28:15

如何使用拓撲排序在有向圖中找到一個循環？

回答

相關問題