问为什么Kruskal和Prim MST算法对稀疏和密集图有不同的运行时？

EN

这些关于顶点数量的复杂性会不会不同呢？

通常，有一个稍微有点手势的论点说，对于稀疏图，边的数量E= O(V)，其中V是顶点的数量，对于稠密图E= O(V^2)。由于这两个算法都可能具有依赖于E的复杂度，当您将其转换为依赖于V的复杂度时，您会得到不同的复杂度，这取决于密集或稀疏图

编辑：

不同的数据结构也会影响复杂性，当然维基百科对this进行了分解

Cormen等人的算法确实给出了分析，在这两种情况下都使用了图的稀疏表示。使用Kruskal的算法(在不相交的组件中链接顶点，直到一切都连接起来)，第一步是对图的边进行排序，这需要O(E，lg，E)，并且他们简单地确定没有比这更长的时间了。使用Prim的算法(通过添加当前树上尚未添加的最近顶点来扩展当前树)，他们使用斐波那契堆来存储挂起顶点的队列，并获得O(E +V lgV)，因为使用斐波那契树减少到队列中顶点的距离仅为O(1)，并且每个边至多执行一次。