关于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），因为任何两个顶点都是通过边连接的。 –

回答