为什么 Kruskal 和 Prim MST 算法对于稀疏图和稠密图有不同的运行时间？
我试图理解为什么 Prim 和 Kruskal 在稀疏图和密集图方面具有不同的时间复杂度。在使用了几个小程序来演示每个小程序的工作原理之后，我仍然对图的密度如何影响算法感到有点困惑。我希望有人能给我一个正确的方向。
I am trying to understand why Prim and Kruskal have different time complexities when it comes to sparse and dense graphs. After using a couple of applets that demonstrate how each works, I am still left a little confused about how the density of the graph affects the algorithms. I hope someone could give me a nudge in the right direction.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
维基百科以边数 E 和顶点数 V 的形式给出了这些算法的复杂性，这是一个很好的实践，因为它可以让你准确地做这样的分析。
Kruskal 算法的复杂度为 O(E log V)。 Prim 的复杂性取决于您使用的数据结构。使用邻接矩阵，其复杂度为 O(V2)。
现在，如果您将 V2 代入 E，您会发现您在评论中引用的密集图的复杂性，并且如果您插入在 V 中 E，你会得到稀疏的。
为什么我们要插入 V2 以获得密集图？好吧，即使在最密集的图中，您也不可能拥有多达 V2 条边，因此显然 E = O(V 2）。
为什么我们要为稀疏图插入V？好吧，您必须定义稀疏的含义，但假设如果每个顶点的边数不超过 5 个，我们将图称为稀疏图。我想说这样的图非常稀疏：一旦达到数千个顶点，邻接矩阵将大部分是空的。这意味着对于稀疏图，E ≤ 5 V，因此 E = O(V)。
Wikipedia gives the complexity of these algorithms in terms of E, the number of edges, and V, the number of vertices, which is a good practice because it lets you do exactly this sort of analysis.
Kruskal's algorithm is O(E log V). Prim's complexity depends on which data structure you use for it. Using an adjacency matrix, it's O(V2).
Now if you plug in V2 for E, behold you get the complexities that you cited in your comment for dense graphs, and if you plug in V for E, lo you get the sparse ones.
Why do we plug in V2 for a dense graph? Well even in the densest possible graph you can't have as many as V2 edges, so clearly E = O(V2).
Why do we plug in V for a sparse graph? Well, you have to define what you mean by sparse, but suppose we call a graph sparse if each vertex has no more than five edges. I would say such graphs are pretty sparse: once you get up into the thousands of vertices, the adjacency matrix would be mostly empty space. That would mean that for sparse graphs, E ≤ 5 V, so E = O(V).
这些不同的复杂性是否与顶点数量有关？
经常有一个稍微有点夸张的说法，对于稀疏图，边的数量 E = O(V)，其中 V 是顶点的数量，对于稠密图，E = O(V^2)。由于两种算法都可能具有取决于 E 的复杂性，当您将其转换为取决于 V 的复杂性时，您会根据密集图或稀疏图获得不同的复杂性
编辑：
不同的数据结构也会影响复杂性，当然维基百科对 < a href="http://en.wikipedia.org/wiki/Prim's_algorithm" rel="nofollow noreferrer">这个
Are these different complexities with respect to the number of vertices by any chance?
there is often, a slightly handwavy, argument that says for a sparse graph, the number of edges E = O(V) where V is the number of verticies, for a dense graph E = O(V^2). as both algotrithms potentially have complexity that depends on E, when you convert this to comlexity that depends on V you get different complexities depending on dense or sparse graphs
edit:
different data structures will also effect the complexity of course wikipedia has a break down on this
Cormen 等人的算法确实给出了分析，在这两种情况下都使用图形的稀疏表示。使用 Kruskal 算法（链接不相交组件中的顶点，直到所有元素都连接起来），第一步是对图的边进行排序，这需要时间 O(E lg E)，并且他们简单地确定没有其他方法需要比这更长的时间。使用 Prim 的算法（通过添加尚未存在的最近的顶点来扩展当前树），他们使用斐波那契堆来存储待处理顶点的队列并获得 O(E + V lgV)，因为斐波那契树减少了到顶点的距离队列中的时间复杂度仅为 O(1)，并且每个边最多执行一次。
Algorithms by Cormen et al does indeed give an analysis, in both cases using a sparse representation of the graph. With Kruskal's algorithm (link vertices in disjoint components until everything joins up) the first step is to sort the edges of the graph, which takes time O(E lg E) and they simply establish that nothing else takes longer than this. With Prim's algorithm (extend the current tree by adding the closest vertex not already on it) they use a Fibonacci heap to store the queue of pending vertices and get O(E + V lgV), because with a Fibonacci tree decreasing the distance to vertices in the queue is only O(1) and you do this at most once per edge.