如何通過循環查找找到最小生成樹？

通過搜索網絡，我可以找到2（kruskal和prims）算法尋找最小生成樹。但是這個算法如何通過循環查找找到最小生成樹？

*let T be initially the set of all edges 
     *while there is some cycle C in T 
     remove edge e from T where e has the heaviest weight in C

我找不到通過搜索網頁。我如何實現這個算法。我怎樣才能找到每個可能的週期？

[循環檢測（http://en.wikipedia.org/wiki/Cycle_detection_（graph_theory）#Cycle_detection）。但是這個算法比Kruskal和Prim的要貴很多。 – Dukeling

按降序對邊進行排序，然後嘗試每次刪除邊。檢查圖形是否連接。如果圖形在刪除邊緣後仍然連接，它將確保邊緣處於一個循環中。

2013-10-22 12:29:17

最簡單的方法是通過Union-Find數據結構（參見下面的鏈接）。檢查週期可以在O（1）時間內完成，並且添加一個新的邊緣需要平均每個節點的O（log V）處理，要求總體運行時間爲O（E + V log V）。我們可以使用更先進的數據結構來實現接近線性的時間範圍。

2013-12-02 07:38:18 neerajprad

回答