Время выполнения приведенного ниже алгоритма алгоритма Прима

Question

Наивное выполнение алгоритма Prim's в Algo должно дать время работы O (mn). Но у меня есть 3 для циклов в Prim-функции (что делает время выполнения кубическим). Где я иду не так?

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/