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

Question

prim 算法的简单实现应该给出 O(mn) 的运行时间。但是我在 Prim 函数中有 3 个 for 循环（使运行时间立方）。我哪里错了？

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/

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

Running Time of The Below Code of Prim's Algorithm

c++

algorithm

graph-algorithm