使無向圖連接斷開的最小開銷

Question

斷開無向加權（正向權重）圖的最小開銷是多少？

我的意思是我必須找出那些刪除斷開圖的邊緣，他們的成本最小化。

我有以下想法...

1.找出圖中的所有橋樑。那麼最小重量的橋邊將是答案。

2.如果沒有橋，那意味着所有的節點都在一個循環中（我不確定它）。那麼我根據它們的權重對邊進行排序，兩個最小邊權重的總和就是ans。

該圖沒有自循環。

這個算法是否正確？

Answer 1

這個問題看起來是圖表中「最小切割」研究所回答的同一問題。我建議閱讀here和here以瞭解更多關於它爲什麼從圖理論的角度來看 - 鏈接也提供了一些僞代碼。

關於您提出的算法，在圖中找到橋可能會變得棘手..您必須檢查兩個端點及其局部結構以確認橋的存在..使用邊緣收縮可能會更容易實現。