如何确定Prim算法中距离更新操作的总数？

Question

在Prim中，在向“云”中添加一个新的顶点U (其中包含所有已访问的顶点)后，我们需要更新云与从U到达的所有顶点之间的距离，您如何找到这些更新操作的上限？

我的教科书上说它是O(m)，m是图中边的数。这将导致整个Prim算法的O(m+n)logn)。

Answer 1

每次将顶点U添加到云中时，只需考虑在U处有一个端点的所有边，因此要将所有顶点添加到云中，每个边都会被考虑两次(每个端点一次)。这给出了2m的界，其中m是图中的边数。

Answer 2

看看此页。最后，解释了当图n= O(m)完全连通时，时间复杂度为O((m+n)log n)和O(m log n)的原因。