BFS or breadth first search or breadth first traversal of a graph is algorithm in which we visit from root node to all adjacent children of  root node. i.e BFS explores its breadth first. Look at the below figure:

bfs

If start node is 0th node then BFS traversal will be: 0 1 2 3  4 5. To achieve this we have to do following steps:

  • Visit the 0th node, and explore all the adjacent children. mark them visited. this is required to track visited node because if we would not mark then we would process each visited node again and again and this would be a non terminating process.

bfs1

To track visited node we use queue. Now all adjacent nodes corresponding to 0th node have been visited now. they all get enqueued and marked visited.

  • Now we have to go at node 1, to do that we look at queue. when we  dequeue  , we get node 1. so now our working node will be node(vertex) 1. since the adjacent child node in given graph is node 4. we explore this node ,mark it visited and enqueue it.

bfs1

 

  • Now there is no place to go from 4. so we dequeue again and will get node 2. Now from node 2, we explore its adjacent node, which is 5. mark node 5 visited and enqueue it. queue members are 5 4 3
  • As there is no place to go from node 5 ,then we dequeue the queue and get node 3. then we have to explore the node 2 and node 4, since these nodes are already visited then no need to explore.  queue members is 5 4 now.
  • now deque que [ 5 4]. we will get 4, since it is already visited, we dequeue again and will get node 5, since it is already visited we dequeue it again.
  • when queue is empty, it shows that algorithm stops and we have visited the graph.

Implementation of BFS using stl queue

#include<iostream>
#include<queue>
#include<list>
#include<string.h>
using namespace std;

class G
{
private:
  bool * visited;
  queue < int >myque;
  list < int >*adj;
public:
  G (int no_of_vertices);
  void doBFS (int start_vertex);
  void addList (int u, int v);
};
G::G (int no_of_vertices)
{
  visited = new bool[no_of_vertices];
  adj = new list < int >[no_of_vertices];
  memset (visited, false, sizeof (visited));
}

void
G::addList (int u, int v)
{
  adj[u].push_back (v);
}

void G::doBFS (int start_vertex)
{
  visited[start_vertex] = true;
  myque.push (start_vertex);

  while (!myque.empty ())
    {
      int u = myque.front ();
      myque.pop ();
      // print vertex
      cout << u << " ";
      list < int >::iterator it;
      for (it = adj[u].begin (); it != adj[u].end (); it++)
    {
      if (!visited[*it])
        {
          visited[*it] = true;
          myque.push (*it);
        }
    }
    }
  cout << "\n";
}

int
main ()
{
  G g (6);
  g.addList (0, 1);
  g.addList (0, 2);
  g.addList (0, 3);
  g.addList (1, 4);
  g.addList (2, 5);
  g.addList (4, 5);
  g.addList (3, 2);
  g.addList (3, 4);
  g.doBFS (0);
  return 0;
}



Related Contents to follow