最小生成树的运行时间？ （Prim方法）

Question

我写了一个使用Prim方法解决MST的代码。我读到这种实现（使用优先级队列）应该有O（E + VlogV）= O（VlogV）其中E是边的数量和V的边数，但是当我查看我的代码时，它根本看不到如果有人能为我解决这个问题，我将不胜感激。

对我来说，似乎运行时间是这样的：

while循环需要O（E）次（直到我们经过所有的边） 在该循环中，我们从需要O将q提取元素（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; 
} 

Answer 1

你可以用邻接表来加速解决方案（但不能用于密集图），但即使是这样，你是不会不斐波那契堆得到O（V登录V）..

也许Kruskal algorithm会让你更容易理解。它没有优先级队列，只需对一组边进行一次排序。它是这样的基本上是：

• 插入所有边缘到一个数组和按重量计
• 遍历排序边缘对它们进行排序，并为每个边缘连接的节点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; 
} 

在开始的时候，只是初始化吨至所有-1，然后每次你想找出是否节点A和B连接，只是比较他们的父母 - 如果他们是相同的，他们是连接（像这样getParent(A)==getParent(B)）。将边缘插入MST时，请务必使用Unite(getParent(A),getParent(B))更新联合查找。

分析很简单，您对边进行排序并使用带有O（1）的UF进行迭代。所以它是O（E logE + E），它等于O（E log E）。

就是它;-)

Answer 2

我没有要处理的算法之前，但你已经实现的算法作为Wikipedia解释的不匹配。那里的算法工作如下。

1. 但是所有的顶点都进入队列。 O（V）
2. 虽然队列不为空... O（V）
   1. ，要考虑与从队列中的最小重量的边缘。 O（log（V））
   2. 更新相邻顶点的权重。 O（E/V），这是相邻顶点的平均数量。
   3. 重新建立队列结构。 O（日志（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) 

一个期望的是什么。