Prim算法的以下代码的运行时间

Question

prim的Algo的朴素实现应该给出O（mn）的运行时间。但是我在Prim函数中有3个循环（使得运行时间立方体）。我哪里错了？

void Graph::Prim (const int src)     //Nodes start from 1 to n-1 
{            // n = Nodes+1. 

    NodeExplored[src] = true; 

    for(int i=1; i<n-1;++i)       //n-2 iterations 
    { 
     int minIndex; 
     int minEW = 10000; 
     int svIndex; 

    for(int sv =1;sv < n;sv++)     //To check for Explored nodes 
     { 
     if(NodeExplored[sv]==true) 
      { 
       for(auto i = G[sv].begin();i!= G[sv].end();++i) 
       {         //To scan through the edges from sv. 

        int dv = i->first;   //Destination Vertex 
        int ew = i->second;   //Edge Weight b/w sv & dv. 

        if(NodeExplored[dv]==false && ew < minEW) 
        { 
         minEW = ew; 
         minIndex = dv; 
         svIndex = sv; 
        } 
       } 
      } 
     } 

    NodeExplored[minIndex] = true; 

    MST[svIndex].push_back(make_pair(minIndex,minEW)); 
    MST[minIndex].push_back(make_pair(svIndex,minEW)); 

    } 

Answer 1

最内层的循环将占大部分节点发现。因此，外环将在条件if(NodeExplored[sv]==true)上失败并且没有做任何事情，因此是O（M^2）时间解决方案。

可以考虑更好的方法，就像不通过所有节点的队列一样（因此外层循环会转换为while循环）。

一个清楚的描述解决方案是这里提出：http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/