如何檢測無向圖中的週期，並在該週期中刪除具有最大權重的邊沿？

我知道DFS或union-find可以用來檢測週期。但是有沒有一種快速的方法來找到那個週期內重量最大的邊緣？如何檢測無向圖中的週期，並在該週期中刪除具有最大權重的邊沿？

2011-11-18 rialmat

沒有比看到所有這些並記住你看到的最大的一個更快。 DFS和聯合查找並不一定能找到任何權重順序的邊，只是按照它們離開始節點的距離的順序排列，所以除非按重量排序，否則不知道哪個週期最大或者其他的東西。 – bdares

你不會試圖做[這個]（http://stackoverflow.com/questions/8178072/finding-a-minimum-spanning-tree-given-the-old-mst-and-a-new-vertex你可以嗎？ – Per

沒有，DFS和順序搜索是最佳的解決方案。只需找到循環，並通過它的邊緣找到最大的重量邊緣。這裏的複雜性並不重要 - 你必須找到這個循環，找到最大邊的複雜性是一樣的。

2011-11-18 03:42:34

有做這只是一次沒有什麼好辦法，但如果你要迭代，直到該圖是無環，你會離開一個最小生成樹，它可以在linearithmic時間來計算。

2011-11-18 03:47:03 Per

回答