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

Question

First I have created an un-directed graph of vertices, edges and weights.

In prims() function:

• vertex[] array is initialized to INT_MAX for all indices i < n except 0 index. It will have smallest weights found till now.
• bool isthere[] array to check either a vertex is visited or not.
• list<int> s at first will have 5 (0-4 indices) values. After each for loop its value will pop.
• vector<int> mset will keep the 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;
}

Here's my adjacency list. It is an array of vector of pairs denoting vertex, weight.

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

Here's the debug output and the error I got in the prims() function.

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.

Answer 1

for(it=adj[i].begin();it!=adj[i].end();++it){
  // ...
  i=it->first;
  // ...
}

This code exhibits undefined behavior, as it compares an iterator into one container with iterator into a different one. it is initialized with, say, adj[0].begin(), then i changes inside the loop, and on the next iteration the iterator is compared with, say, adj[1].end()