Реализация алгоритма Prim в ошибке C++ STL?

Question

Я пытаюсь реализовать алгоритм MST Prim в C++ с использованием STL.

Но для следующей программы он, кажется, входит в бесконечный цикл. А затем выходит с ошибкой.

Псевдокод для алгоритма MST Prim;

Мой код:

#include<algorithm> 
#include<vector> 
#include<iostream> 
#include<queue> 
using namespace std; 

typedef vector<int>   vi; 
typedef pair<int,int>  ii; 
typedef vector<ii>   vii; 

#define REP(i,a,b) for(int i=int(a);i<b;i++) 
#define TRvii(c,it) for(vii::iterator it=(c).begin();it!=(c).end();it++) 

#define INF 2000000000 

void Prims(int V, int s, vector<vii> &AdjList) 
{ 
    vector<int> dist(V,INF); 
    dist[s] = 0; 
    priority_queue<ii,vector<ii>,greater<ii> > pq; 
    pq.push(ii(0,s)); 

    REP(i,1,V) pq.push(ii(i,INF)); 

    bool inPriorityQueue[V]; 
    REP(i,0,V) inPriorityQueue[i] = true; 

    while(!pq.empty()) 
    { 
     ii top = pq.top(); pq.pop(); 
     int d = top.first,u = top.second; 

     inPriorityQueue[u] = false; 

     TRvii(AdjList[u],it) 
     { 
      int v = it->first, weight_u_v = it->second; 

      if(inPriorityQueue[v] && weight_u_v<dist[v]) 
      { 
       dist[v] = weight_u_v; 
      } 
     } 
    } 

    cout << "The shortest distance from " << s << " to all the nodes is" << endl; 
    REP(i,0,V) 
    { 
     cout << i << " : " << dist[i] << endl; 
    } 
} 

int main() 
{ 
    int v,s,edges; 

    printf("Enter number of vertices : "); 
    scanf("%d",&v); 

    vector<vii> adjList(v+1); 

    printf("\nEnter source vertex : "); 
    scanf("%d",&s); 

    adjList[0].push_back(make_pair(1,4)); 
    adjList[0].push_back(make_pair(7,8)); 
    adjList[1].push_back(make_pair(0,4)); 
    adjList[1].push_back(make_pair(2,8)); 
    adjList[1].push_back(make_pair(7,11)); 
    adjList[7].push_back(make_pair(0,8)); 
    adjList[7].push_back(make_pair(1,11)); 
    adjList[7].push_back(make_pair(8,7)); 
    adjList[7].push_back(make_pair(6,1)); 
    adjList[2].push_back(make_pair(1,8)); 
    adjList[2].push_back(make_pair(3,7)); 
    adjList[2].push_back(make_pair(8,2)); 
    adjList[2].push_back(make_pair(5,4)); 
    adjList[8].push_back(make_pair(2,2)); 
    adjList[8].push_back(make_pair(7,7)); 
    adjList[8].push_back(make_pair(6,6)); 
    adjList[6].push_back(make_pair(7,1)); 
    adjList[6].push_back(make_pair(5,2)); 
    adjList[6].push_back(make_pair(8,2)); 
    adjList[5].push_back(make_pair(6,2)); 
    adjList[5].push_back(make_pair(2,4)); 
    adjList[5].push_back(make_pair(3,14)); 
    adjList[5].push_back(make_pair(4,10)); 
    adjList[4].push_back(make_pair(3,9)); 
    adjList[4].push_back(make_pair(5,10)); 
    adjList[3].push_back(make_pair(2,7)); 
    adjList[3].push_back(make_pair(5,14)); 
    adjList[3].push_back(make_pair(4,9)); 

    Prims(v, s, adjList); 

    return 0; 
} 

график, на котором реализован этот алгоритм:

Answer 1

Если бы вы пытались ее отладки вы бы очень быстро нашли проблему лежит на линии:

TRvii(AdjList[u],it) 

Подумайте, что такое u. При первом обходе вокруг петли whileu == s из-за pq.push(ii(0,s));. В следующем и последующих циклах, однако, u == INF из-за REP(i,1,V) pq.push(ii(i,INF));.

Попытка получить доступ AdjList[INF] является «плохим» и приводит к неопределенному поведению (авария в вашем случае).

Я бы предложил отладить ваш алгоритм дальше, возможно, с более простым тестовым примером. Пройдите через него и посмотрите все переменные. Предположительно, вы понимаете алгоритм и какие состояния он должен пройти, поэтому следите за всеми переменными, чтобы убедиться, что они такие, какими они должны быть.