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