最小生成树的运行时间是多少？（Prim算法）

Question

我已经编写了一段代码，使用Prim方法解决MST问题。我读到这种实现方式（使用优先队列）应该具有O(E + VlogV) = O(VlogV)的时间复杂度，其中E是边的数量，V是点的数量，但是当我看我的代码时，它似乎并不是这样。如果有人能为我解释一下，我将不胜感激。

在我看来，运行时间如下： while循环需要O(E)次（直到我们遍历完所有的边） 在该循环内部，我们从Q中提取一个元素，需要O(logE)的时间。 第二个内部循环需要O(V)的时间（虽然我们不总是运行此循环，但显然它将被运行V次，因为我们必须添加所有的顶点）

我的结论是，运行时间为：O( E(logE+V) ) = O( E*V )。

这是我的代码:

#define p_int pair < int, int >

int N, M; //N - nmb of vertices, M - nmb of edges
int graph[100][100] = { 0 }; //adj. matrix
bool in_tree[100] = { false }; //if a node if in the mst
priority_queue< p_int, vector < p_int >, greater < p_int > > Q; 
/*
keeps track of what is the smallest edge connecting a node in the mst tree and
a node outside the tree. First part of pair is the weight of the edge and the 
second is the node. We dont remember the parent node beaceuse we dont need it :-)
*/

int mst_prim()
{
 Q.push( make_pair( 0, 0 ) );

 int nconnected = 0;
 int mst_cost = 0;
 while( nconnected < N )
 {
      p_int node = Q.top(); Q.pop();

      if( in_tree[ node.second ] == false )
      {
           mst_cost += node.first;
           in_tree[ node.second ] = true;

           for( int i = 0; i < N; ++i )
                if( graph[ node.second ][i] > 0 && in_tree[i]== false )
                     Q.push( make_pair( graph[ node.second ][i], i ) );

           nconnected++;
      }
 }

 return mst_cost;
}

- synepis

Answer 1

您可以使用邻接表来加速解决方案（但不适用于稠密图），但即使如此，如果没有斐波那契堆，您也无法获得O（V log V）的时间复杂度。也许Kruskal算法更容易理解一些。它不需要优先队列，您只需要对边的数组进行一次排序。基本上是这样的：

• 将所有边插入数组并按权重排序
• 遍历已排序的边，并针对连接节点i和j的每条边，检查i和j是否已连接。如果已连接，则跳过该边，否则将该边添加到MST中。

唯一的问题是要快速确定两个节点是否连接。为此，您可以使用并查集数据结构，其基本思路如下：

int T[MAX_#_OF_NODES]

int getParent(int a)
{
  if (T[a]==-1)return a;
  return T[a]=getParent(T[a]);
}
void Unite(int a,int b)
{
  if (rand()&1)
     T[a]=b;
  else
     T[b]=a;
}

起初，只需将T初始化为-1，然后每次想要查找节点A和B是否相连时，只需比较它们的父节点 - 如果它们相同，则它们是相连的（例如这样：getParent（A）== getParent（B））。当您将边插入MST时，请确保使用Unite（getParent（A），getParent（B））更新Union-Find。

分析很简单，您对边进行排序，然后使用UF进行迭代，这需要O（1）。所以它是O（E logE + E ），这等于O（E log E）。

就是这样;-)

- supo

---

我知道Kruskal算法，但我也想了解这个算法 :-）。如果我在Prim算法中使用邻接表，那么我会得到：while + for循环遍历所有边并将它们插入堆中。这应该是E*log(E)。使用这种方法（使用堆而不是Fibbonaci堆），这是您可以获得的最佳复杂度吗？ - synepis

是的，你最多检查每条边两次（从两个节点），队列最多有E条边，这导致O(E log E)。但我们不会这样写，因为常数因素在O()符号中是无关紧要的。因此，O(E log E) = O(E log (V^2)) = O(E * 2 log V) = O(E log V)。 - supo

这（上面的评论）就是我想要的答案，谢谢，现在我懂了 :-) - synepis

Answer 2

我以前没有处理过这个算法，但是你实现的方式与维基百科上所解释的算法不匹配。那里的算法如下：

1. 将所有顶点放入队列中。O(V)
2. 当队列不为空时... O(V)
   1. 从队列中选取具有最小权重的边。O(log(V))
   2. 更新相邻顶点的权重。O(E/V)，即相邻顶点的平均数量。
   3. 重新建立队列结构。O(log(V))

这给出了

        O(V) + O(V) * (O(log(V)) + O(V/E))
      = O(V) + O(V) * O(log(V)) + O(V) * O(E / V)
      = O(V) + O(V * log(V)) + O(E)
      = O(V * log(V)) + O(E)

正是人们所期望的。

- Daniel Brückner

---

我不太确定是否要在开头插入所有顶点... 如何提取权重最小且连接到当前正在构建的最小生成树（mst）的顶点？ - synepis

每个顶点的优先级是将该顶点与当前生成树连接的成本 - 这是连接该顶点与当前树的所有边的最小权重，如果没有边，则为无穷大。所有这些值都初始化为无穷大，并在每次从队列移动顶点到树时更新。 - Daniel Brückner