C/C++ Graph Implementation using STL C++

[Saitama]

I am trying to implement a graph and perform BFS on it in C++. Following is the code I have written so far:

#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 code works fine till the point when "cout<<BFS(0)" is called. I get a runtime error when the function BFS is executed. I do not have much experience with using iterators in C++ so I believe the error comes from the iterator statements in BFS function.

Any help is appreciated. Thanks!

 

[johng1]

Pranav,
I'm not quite sure if your question is one involving C++ iterators or the breadth first search algorithm applied to a component of a graph. However, the main problem in your code is that you have not implemented BFS correctly. Maybe you know this, but I'll repeat.

A graph consists of vertices (non-negative ints) and edges. This may be implemented with an array a of lists were a is the "adjacency" list of vertices j such that {i,j} is an edge of the graph. (For a graph (not a digraph), if j appears on list a, i appears on a[j].)

Now BFS is an algorithm with input a vertex s. The algorithm traverses (visits) all vertices in the component of the graph containing s. That is a vetex i is visited iff i is reachable from s (there is a sequence s=v0, v1, ... vn=i where a pair of adjacent vertices in the sequence is an edge of the graph).

The algorithm is implemented with a queue Q. The idea is that during the execution of the algorithm each vertex i reachable from s appears exactly once in Q. This is accomplished by initially "marking" all vertices as not visited, enqueue s and then mark s as "visited". Then

 while Q is not empty {
       remove the front vertex x from Q;
       for each vertex i adjacent to x {
             if i is not marked as visited, "visit" i, mark i as visited and add i to Q
       }
   // the above is accomplished by walking down (traversing) the adjacency list a[x]
}

The validity of the algorithm can be proved by induction on the minimal path length from s to a vertex i in the component containing s.

Here's your program with a corrected BFS:

#include <cstdlib>
#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;
   cout << " " << s << " "; // "visit" s
   Q.push(s);
   while (!Q.empty()) {
      int x = Q.front();
      Q.pop();
      list<int>::iterator iter = a[x].begin();
      while (iter != a[x].end()) {
         if (visited[*iter] == 0) {
            visited[*iter] = 1;
            // "visit" vertex *iter
            cout << " " << *iter << " ";
            Q.push(*iter);
         }
         ++iter;
      }
   }
   cout << endl;
   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;
}

 

[Saitama]

Thank you very much johng. I found the error later but forgot to respond here. :)

Sorry for the late response.