Prim's Algorithm implementation in C++ STL error? -

Prim's Algorithm implementation in C++ STL error? -

i trying implement prim's mst algorithm in c++ using stl.

but next programme seems come in in infinite loop. , exits error.

pseudo-code prim's mst algorithm ;

my code :

#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 " << s << " nodes is" << endl; rep(i,0,v) { cout << << " : " << 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); homecoming 0; }

graph on algorithm implemented :

if had tried debugging have found problem lies line:

trvii(adjlist[u],it)

think u is. in first go around while loop u == s due pq.push(ii(0,s));. in next, , subsequent loops however, u == inf due rep(i,1,v) pq.push(ii(i,inf));.

trying access adjlist[inf] "bad" , results in undefined behaviour (a crash in case).

i suggest debugging algorithm further, perchance simpler test case. step through , watch variables. assumably understand algorithm , states should go through watch variables create sure should be.

c++ algorithm graph stl prims-algorithm