algorithm - Prim 算法与 Fibonacci 堆 : why O(E + V*log(V))?

Question

我知道 Prim 的算法以及如何实现它。我也知道为什么它的时间复杂度是 O(E + V log(V))。

我们添加边 E 次(即 O(E))并选择最小 V 次(即 O(V*log(V)))。但我不明白其中的一部分:为什么是 V 次？ !我知道一棵树有 V-1 条边，但如果最重的边必须在 MST 中，我们必须选择最小 E 次，而不是 V 次。

例如:一个完全图，每条边的权重为 1，除了一个顶点，所有连接到它的边的权重为 10^18。

Answer 1

您想使用初始图中的边连接 V 个顶点，形成一棵树。您可以从任何节点开始，比方说 v。然后您将可以从 v 到达的所有顶点以及连接它的边的成本添加到您的队列中。你去成本最低的那个。现在你做同样的事情。如果您想将已经在队列中的顶点 u 放入队列中，则必须检查其边缘的工资。如果新的较小，则取出旧的并插入较新的，如果不是，则跳过它。此外，如果您已经将节点 u 连接到您的树，您也可以跳过它。所以你的队列中最多有 V 个顶点，使得时间复杂度为 O (E + V log V)(E - 因为你必须检查每个顶点的所有边)

编辑:更具体地说，当您再次将顶点 u 添加到队列中时，您可以删除前一个顶点，或者只更改它的成本。如果您使用 Fibonacci 堆，另一件事应该会更快。删除将花费你 O(E log V) 而不是 O(E + VlogV)