關於MST的一些問題

我現在正在學習最小生成樹的主題，並且我理解它的大部分內容，但是我仍然有一些我不明白的東西。我正在處理無向加權圖。關於MST的一些問題

首先，我知道找到MST花費O（E * log V）。現在，當我們處理平面圖時，我想優化它到線性時間 - O（V + E）。其次，我看到了單位平方中有n個點的例子，並且我成功地證明了存在權重爲O（sqrt n）的MST。問題是我找不到找到這個MST的算法。

感謝所有，或者

在平面圖中，最多有3個| V | - 6個邊，所以E = O（V），所以O（V + E）簡化爲O（V）。我不知道專門用於平面圖的O（V）算法，但您可能在網上搜索文獻時有一些運氣。關於在單位平方中找到n個點的MST：爲什麼不使用普通算法，如Prim's或Kruskal's？ –

平面圖：我沒有找到任何東西，所以我試着在這裏解釋一些方向。 MST：我想過爲MST做一個常規算法。這是一個令人滿意的解 –

然後你看起來並不很努力。谷歌搜索「平面最小生成樹」爲我帶來了一頁結果，其中第四個鏈接是一個包含1994年Matsui論文的引用網頁，名爲「平面圖上的最小生成樹問題」。 –

Boruvka的算法運行在平面圖O（V）時間。有關詳情請參閱

此外，您還可以計算的n個點的歐氏MST在澳平面通過計算德勞內三角化邊緣的MST（N log n）的時間。

2014-06-05 18:27:03 ford

非常感謝，這非常有幫助！ –

+1爲Boruvka的算法，但我沒有得到有關使用Delaunay三角剖分歐幾里得MST的部分。這樣做的速度比僅僅構建一個完整的圖表要快嗎？ –

@j_random_hacker構建一個完整的圖需要Theta（n^2），因爲任何兩個頂點都是通過邊連接的。 –

回答