logo标签列表

Prim最小生成树算法的时间复杂度

algorithmgraphtime-complexityminimum-spanning-treeprims-algorithm
7
有人能为我解释一下，为什么Prim算法使用邻接矩阵会导致时间复杂度为O(V2)？
请访问http://cs.stackexchange.com - daniel gratzer
3个回答
8
注意：本答案仅借鉴了jozefg's answer，并尝试更全面地解释它，因为我在理解之前必须思考一下。
背景
图的邻接矩阵表示构建一个V x V矩阵（其中V是顶点数）。单元格(a, b)的值是连接顶点a和b的边的权重，如果没有边，则为零。
Adjacency Matrix

   A B C D E
--------------
A  0 1 0 3 2
B  1 0 0 0 2
C  0 0 0 4 3
D  3 0 4 0 1
E  2 2 3 1 0
普里姆算法是一种算法，它接受一个图和一个起始节点，并在该图上找到最小生成树 - 即找到一个子集，使结果为包含所有节点且组合边权值最小的树。可以概括如下：
  1. 将起始节点放入树中。
  2. 重复直到所有节点都在树中：
    1. 查找连接树中节点和不在树中节点的所有边。
    2. 在这些边中选择一条具有最小权重的边。
    3. 将该边和连接的节点添加到树中。

分析

我们现在可以开始分析算法：

  1. 在每次循环迭代中，我们向树中添加一个节点。由于有V个节点，因此可以得出该循环的迭代次数为O（V）。
  2. 在每次循环迭代中，我们需要查找和测试树中的边缘。如果有E条边，则使用朴素搜索实现查找具有最小权重的边缘的时间复杂度为O（E）。
  3. 因此，在组合中，我们应该期望复杂度为O（VE），在最坏情况下可能为O（V^3）。

然而，jozefg给出了一个好答案，展示了如何实现O（V ^ 2）的复杂度。

Distance to Tree

            | A  B  C  D  E
            |----------------
Iteration 0 | 0  1* #  3  2
          1 | 0  0  #  3  2*
          2 | 0  0  4  1* 0
          3 | 0  0  3* 0  0
          4 | 0  0  0  0  0

NB. # = infinity (not connected to tree)
    * = minimum weight edge in this iteration

这里的距离向量表示连接每个节点到树的最小加权边，并用于以下操作：

  1. 将边权重初始化为起始节点A，复杂度为O(V)。
  2. 要找到下一个要添加的节点，只需找到distance的最小元素（并将其从列表中删除）。 这是O(V)。
  3. 添加新节点后，有O(V)个新边将树连接到剩余节点; 对于这些边中的每一个，确定新边是否比现有距离更小。 如果是，则更新distance向量。同样，O(V)。

使用这三个步骤将搜索时间从O(E)降低到O(V)，并在每次迭代中添加额外的O(V)步骤来更新distance向量。由于每次迭代现在都是O(V)，因此总复杂度为O(V^2)。

这个答案太棒了！这应该是正确的答案！ - Dylanthepiguy
8

传统的Prim算法实现方式是使用一个数组来存储除邻接矩阵外的信息，我们称之为distance，它表示该顶点到节点的最小距离。这样，我们只需检查distance以找到下一个目标，由于我们需要执行V次操作，而distance有V个元素，因此我们的时间复杂度为O(V^2)。

仅凭这些还不够，因为distance中的原始值很快就会变得过时。为了更新这个数组，我们只需在每一步结束时遍历邻接矩阵并适当地更新distance即可。这不会影响我们的时间复杂度，因为这仅意味着每一步需要O(V+V) = O(2V) = O(V)的时间。因此，我们的算法是O(V^2)。

如果不使用distance，则每次都必须遍历所有E个边，最坏情况下包含V^2条边，这意味着我们的时间复杂度将是O(V^3)。

证明：

为了证明没有distance数组时不可能在O(V^2)的时间内计算MST，考虑到在大小为n的树上的每次迭代中，有V-n个顶点可能会被添加。

要计算应选择哪一个，我们必须检查它们中的每一个以找到它们与树的最小距离，然后将其与其他节点进行比较并找到最小值。

在最坏的情况下，每个节点都包含到树中每个节点的连接，导致有n * (V-n)条边，时间复杂度为O(n(V-n))。

由于我们的总和是每个步骤的总和，而n从1变化到V，因此我们的最终时间复杂度为：

(sum O(n(V-n)) as n = 1 to V) =  O(1/6(V-1) V (V+1)) = O(V^3)

QED

传统的Prim算法实现方式是使用一个数组来辅助邻接矩阵，我们称之为距离(distance)数组，它记录了每个顶点到节点的最小距离。这种方式的时间复杂度为O(V^2)。您能详细说明一下这个数组是什么以及里面存放的内容吗？另外，“让我们称之为”中的“它”指的是数组还是邻接矩阵？ - Dylanthepiguy
请忽略我的上面评论，下面有人写了更好的解释。 - Dylanthepiguy
0

首先，显然至少是O(V^2)，因为邻接矩阵的大小就是这么大。

看一下http://en.wikipedia.org/wiki/Prim%27s_algorithm，你需要执行“重复直到Vnew = V” V次的步骤。

在这个步骤中，你需要计算出V中任何一个顶点和V外任何一个顶点之间的最短链接。维护一个大小为V的数组，对于每个顶点，要么是无穷大（如果该顶点在V中），要么是任何一个顶点与该顶点之间的最短链接及其长度（因此在开始时，这仅来自起始顶点与每个其他顶点之间的链接长度）。要找到要添加到V中的下一个顶点，只需搜索这个数组，成本为V。一旦你有了一个新的顶点，就查看从该顶点到每个其他顶点的所有链接，并查看它们是否提供了从V到该顶点的更短链接。如果是，更新数组。这也需要成本V。

因此，你有V个步骤（V个顶点要添加），每个步骤花费V，这给出O(V^2)。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接