I am trying to make prims algorithm using c++ stl .After the iterator iterates 1st time it stops the code and give wrong output

  c++, minimum-spanning-tree, prims-algorithm, stl

First i have created a unidirected graph of vertices, edges and weights.
In prims function vertex[] array have INT_MAX except 0 index. It will have smallest weights according to their between two vertex. bool isthere[] array to check either a vertex is visited or not. list s at first it will have 5, 0-4 values after each for loop its value will pop. Vector mset[] it will keep the vertex,vertex chosen according to their smallest weight.

#include<bits/stdc++.h>
using namespace std;

void addEdge(vector<pair<int,int>>adj[],int u,int v,int wt){
    adj[u].push_back(make_pair(v,wt));
    adj[v].push_back(make_pair(u,wt));
}
void print(vector<pair<int,int>>adj[],int v){
    for(int i=0;i<v;++i){
        cout<<i<<"-->";
        vector<pair<int,int>>::iterator it;
        for(it=adj[i].begin();it!=adj[i].end();++it){
            cout<<it->first<<"-"<<it->second<<" ";
        }
        cout<<"n";
    }
}
void prims(vector<pair<int,int>>adj[],int v){
    int vertex[v];
    bool isthere[v];
    vertex[0]=0;
    isthere[0]=true;
    list<int>s;
    s.push_back(0);
    for(int i=1;i<v;++i){
        vertex[i]=INT_MAX;
        isthere[i]=false;
        s.push_back(i);
    }
    vector<int>mset;
    int i=0;
    while(!s.empty()){
    isthere[i]=true;
    mset.push_back(i);
    s.pop_back();
    cout<<"i="<<i<<" ";
    int lesser=INT_MAX;
    vector<pair<int,int>>::iterator it;
    for(it=adj[i].begin();it!=adj[i].end();++it){
            cout<<"it-"<<it->first<<" "<<it->second<<"n";
        if(isthere[it->first]==false && vertex[it->first]>it->second){
          if(lesser>it->second){
                lesser=it->second;
                i=it->first;
                cout<<"i="<<i<<" ";
            }
          vertex[it->first]=it->second;

        }
    }
    }
}
int main(){
    int v=5;
    vector<pair<int,int>>adj[v];
    addEdge(adj,0,1,2);
    addEdge(adj,0,2,8);
    addEdge(adj,1,3,21);
    addEdge(adj,4,1,6);
    addEdge(adj,2,1,0);
    addEdge(adj,2,4,5);
    addEdge(adj,3,4,9);
    print(adj,v);
    prims(adj,v);
    return 0;
}
[0–>1-2 2-8

1–>0-2 3-21 4-6 2-0

2–>0-8 1-0 4-5

3–>1-21 4-9

4–>1-6 2-5 3-9

i=0 it-1 2

i=1 it-2 8

it-0 0

it- -874898181 134251312

Process returned -1073741819 (0xC0000005) execution time : 0.835 s
Press any key to continue.]1

Source: Windows Questions C++

LEAVE A COMMENT