c++ - 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/