我知道 Prim 的算法以及如何实现它。我也知道为什么它的时间复杂度是 O(E + V log(V))。
我们添加边 E 次（即 O(E)）并选择最小 V 次（即 O(V*log(V)）。但我不明白其中的一部分：为什么 V 次？！我知道一棵树有 V-1 条边，但如果最重的边必须在 MST 中，我们必须选择最少 E 次，而不是 V 次。
例如：一个完整的图，每条边的权重为 1，除了一个顶点，所有连接到它的边的权重为 10^18。
问问题
1004 次
1 回答
2
您想使用初始图中的边连接 V 个顶点，制作一棵树。您可以从任何节点开始，比如说 v。然后将可以从 v 到达的所有顶点添加到队列中，并以连接它的边的成本为代价。你去成本最低的那个。现在你做同样的事情。如果您想将已经在队列中的顶点 u 放入队列中，则必须检查其边缘的工资。如果新的较小，则取出旧的并插入新的，如果没有，则跳过它。此外，如果您已经将节点 u 连接到您的树，您也可以跳过它。所以你的队列中最多有 V 个顶点，使得时间复杂度 O (E + V log V) (E - 因为你必须检查每个顶点的所有边)
编辑：更具体地说，当您再次将顶点 u 添加到队列中时，您可以删除前一个，或者只是更改它的成本。如果您使用斐波那契堆，另一件事应该会更快。删除将花费您 O(E log V) 而不是 O(E + VlogV)
于 2018-07-10T14:16:18.983 回答