2
可能重複：
Best algorithm for detecting cycles in a directed graph在有向圖中循環識別的高效算法？
我在尋找一種算法來尋找有向圖中的循環。
我的圖只在節點中有標籤，而不在邊上，它可以變得非常大。
該算法的輸出應該是循環作爲一組列表，每個列表應包含循環中涉及的節點的標籤，因此列表中的第一個和最後一個元素應該是相同的。
我正在使用的圖很可能只有一個連接組件，而且沒有強連接的組件。預計週期數很低（我仍然需要檢查）。
對於這個或其他類似的任何好算法都是值得歡迎的。
非常感謝。
PS：如果事情是不明確隨時問我要更多的細節，例如，圖形存儲（到目前爲止）爲一組邊集合，從一個節點到多個節點，通常一，這應該是無關緊要的，恕我直言。
是的，但沒有。問題是強連通的組件可能包含許多週期。因此，很難確定要移除的最小節點數量，以便結果中沒有周期。 – jmora 2011-07-06 16:18:28