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

Question

我试图理解为什么 Prim 和 Kruskal 在稀疏图和密集图方面具有不同的时间复杂度。在使用了几个小程序来演示每个小程序是如何工作的之后，我仍然对图的密度如何影响算法感到有些困惑。我希望有人能给我一个正确的方向。

Answer 1

Wikipedia 根据E（边数）和V（顶点数）给出了这些算法的复杂性，这是一个很好的做法，因为它可以让您准确地进行此类分析。

Kruskal 的算法是 O( E log V )。Prim 的复杂性取决于您使用的数据结构。使用邻接矩阵，它是 O( V ² )。

现在，如果你为E插入V ²，你会得到你在评论中引用的密集图的复杂性，如果你为E插入V，你会得到稀疏的。

为什么我们要插入V ²以获得密集图？好吧，即使在最密集的图中，你也不能有尽可能多的V ²边，所以很明显E = O( V ² )。

为什么我们为稀疏图插入V ？好吧，您必须定义稀疏的含义，但是假设如果每个顶点的边不超过五个，我们将其称为稀疏图。我会说这样的图非常稀疏：一旦你进入数千个顶点，邻接矩阵将大部分是空白空间。这意味着对于稀疏图，E ≤ 5 V，因此E = O( V )。

Answer 2

这些关于顶点数量的不同复杂性是否有任何机会？

对于稀疏图，通常有一个稍微手摇的论点，边数 E = O(V)，其中 V 是顶点数，对于密集图 E = O(V^2)。由于两种算法都可能具有取决于 E 的复杂性，因此当您将其转换为取决于 V 的复杂性时，您会根据密集或稀疏图获得不同的复杂性

编辑：

不同的数据结构也会影响维基百科的复杂性

Answer 3

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