遞歸最小生成樹算法

Question

這是尋找最小生成樹的正確算法。

將圖劃分爲2個等同連接的部分。找到它最小的生成樹。用連接它們的最小邊連接它們。我試圖得到這個算法的反例，但是不能。

Answer 1

考慮一個四節點圖，連接成一個正方形，左邊的成本爲10，所有其他邊的成本爲1.如果將遞歸圖的左右分爲兩部分，則最終會得到生成樹的成本爲12，而不是成本3.

MST不適合「分而治之」的算法。最接近的可能是Reverse-Delete算法;每當你不能刪除邊緣（因爲它會斷開圖形），你可以將剩下的步驟想象成在邊緣的兩邊遞歸執行。