如何使用堆來優化Prim的最小生成樹算法？

Question

我必須解決一個類似這樣的問題：
我給了一個數字N來表示我擁有的點數。每個點具有兩個座標：X和Y

我能找到用下列公式兩個點之間的距離：
ABS（X2-X1）+ ABS（Y2-Y1），
（ x1，y1）爲第一點的座標，（x2，y2）爲第二點的座標，絕對值爲abs()。

我必須找到最小生成樹，這意味着我必須讓所有的點與邊的總和最小。 Prim的算法很好，但它太慢了。我讀到，我可以使用heap使其更快，但我沒有找到解釋如何做到這一點的任何文章。

任何人都可以解釋一下Prim的算法是如何處理堆的（一些示例代碼會很好，但不是必須的），請問？

Answer 1

可以有效地解決這個問題（在O(n log n)時間），但並不那麼容易。僅僅使用Prim算法和堆並不能幫助（它實際上使得它更慢），因爲它的時間複雜度是O(E log V)，在這種情況下是O(n^2 * log n)。

但是，您可以使用Delaunay三角剖分來減少圖形中的邊數。 Delaunay三角剖分圖是平面的，因此它具有線性數量的邊緣。這就是爲什麼運行帶有堆的Prim算法時間複雜性（有O(n)邊和n頂點）。你可以在這裏閱讀更多關於它的信息（詳細說明這個算法並證明它的正確性會讓我的回答方式太長）：http://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree。請注意，儘管文章是關於歐幾里得mst，但您的案例的方法基本相同（也可以有效地爲曼哈頓距離構建Delaunay三角剖分）。

Prim的算法與堆本身的描述已經出現在你的問題的其他兩個答案中。

Answer 2

從維基百科的文章上Prim's algorithm：

[S] toring頂點，而不是邊緣可以進一步改善它。堆應該用最小的邊權重來排序頂點，這個最小的邊權重將它們連接到部分構建的最小生成樹（MST）中的任何頂點（或者如果沒有這樣的邊存在，則爲無窮大）。每次選擇頂點並將其添加到MST時，在部分MST外部的所有頂點和上執行減鍵操作，使得v連接到w，將鍵設置爲其先前值的最小值和邊緣成本（v，w）。