Implementing graph and BFS in C++ using STL

Question

Following is the code I have written.

#include <iostream>
#include <vector>
#include <list>
#include <queue>

using namespace std;

const int V=5;
vector<list<int> > a(V);

int BFS(int s)
{
    int visited[V]={0};
    queue<int> Q;
    visited[s]=1;
    Q.push(s);
    while(!Q.empty())
    {
        int x=Q.front();
        vector<list<int> >::iterator it1=a.begin()+x;
        list<int> it2=*it1;
        list<int>::iterator iter=it2.begin();
        while(iter!=it2.end())
        {
            if(visited[*iter]==0)
            {
                visited[*iter]=1;
                Q.push(*iter);
            }
            visited[x]=2;
            Q.pop();
            iter++;
        }
    }
    return 0;
}

void addEdge(int i, int j)
{
    a[i].push_back(j);
    a[j].push_back(i);
}

int main() {
    vector<list<int> >::iterator it1=a.begin();
    addEdge(0,1);
    addEdge(0,2);
    addEdge(2,1);
    while(it1!=a.end())
    {
        list<int> it2=*it1;
        list<int>::iterator iter=it2.begin();
        while(iter!=it2.end())
        {
            cout<<*iter<<" ";
            iter++;
        }
        cout<<endl;
        it1++;
    }
    cout<<BFS(0);
    return 0;
}

The compiler gives me a runtime error when BFS(0) is executed. Since I do not have much experience with iterators, I think the error comes from the iterator statements in the BFS function. Please help me resolve the issues in my code.

Thank you!

Answer 1

Your pop-logic is wrong. It should look like this:

int BFS(int s)
{
    int visited[V]={0};
    queue<int> Q;
    visited[s]=1;
    Q.push(s);
    while(!Q.empty())
    {
        int x=Q.front();
        Q.pop(); // pop here. we have x now

        vector<list<int> >::iterator it1=a.begin()+x;
        list<int> it2=*it1;
        list<int>::iterator iter=it2.begin();
        while(iter!=it2.end())
        {
            if(visited[*iter]==0)
            {
                visited[*iter]=1;
                Q.push(*iter);
            }
            ++iter;
        }

        visited[x]=2; // set visited here.
    }
    return 0;
}

Calculation of the final value I leave to you, as I imagine you want something besides zero always being returned. However, that was the crux of your problem.

Best of luck.