Breadth first search (BFS) and Depth first search (DFS) for a Graph in C++

In this tutorial we will learn about the traversal (or search) of the graph by using the two approaches, one is the breadth-first search (BFS) and another one is depth-first search (DFS). Here we will also see the algorithm used for BFS and DFS.

In BFS, we start with the starting node and explores all the neighbouring node and then select the one by one neighbouring nodes(using queue) and explores its unvisited neighbouring nodes. While in DFS we go to depth as possible from starting node.

BFS  and DFS for the Graph

First, we will look at the algorithm for BFS.

1. Take the empty queue and bool type array (visit) initialise with FALSE.
2. Push the starting node in the queue and set the value TRUE for this node in visited array.
3. Pop out the front node of the queue and print the node.
4. Push the adjacent node of pop node in queue which are not visited. Set the value TRUE in visited array of  adding node.
5. Repeat step 3 and 4 until the queue becomes empty.

Now we will look on the algorithm for DFS.

1. Take the empty stack and bool type array (visit) initialise with FALSE.
2. Push the starting node in the stack and set the value TRUE for this node in visited array.
3. Pop the top node from the stack and print that node.
4. Push the adjacent node of pop node in the stack which is not visited. Set the value TRUE in visited array of adding node.
5. Repeat step 3 and 4until the stack becomes empty.

So, here we also look that the BFS and DFS algorithm is mostly similar in above iterative approaches, only one difference is that in BFS that we will use the queue and in DFS we will use the stack because need goes to depth for DFS.

Implementation of the graph is by the method of an adjacency list. Therefore Implementation of adjacency list is by the using of the vector of an array:-

vector<int>adj[5]; //vector of array to store the edge 

C++ code implementation for BFS and DFS :-

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
//add the edge in graph
void edge(vector<int>adj[],int u,int v){
  adj[u].push_back(v);
}
//function for bfs traversal
void bfs(int s,vector<int>adj[],bool visit[]){
  queue<int>q;//queue in STL
  q.push(s);
  visit[s]=true;
  while(!q.empty()){
    int u=q.front();
    cout<<u<<" ";
    q.pop();
//loop for traverse
    for(int i=0;i<adj[u].size();i++){
      if(!visit[adj[u][i]]){
        q.push(adj[u][i]);
        visit[adj[u][i]]=true;
      }
    }
  }
}
//function for dfs traversal
void dfs(int s,vector<int>adj[],bool visit[]){
  stack<int>stk;//stack in STL
  stk.push(s);
  visit[s]=true;
  while(!stk.empty()){
    int u=stk.top();
    cout<<u<<" ";
    stk.pop();
//loop for traverse
    for(int i=0;i<adj[u].size();i++){
      if(!visit[adj[u][i]]){
        stk.push(adj[u][i]);
        visit[adj[u][i]]=true;
      }
    }
  }
}
//main function
int main(){
  vector<int>adj[5];//vector of array to store the graph
  bool visit[5];//array to check visit or not of a node
  //initially all node are unvisited
  for(int i=0;i<5;i++){
    visit[i]=false;
  }
  //input for edges
  edge(adj,0,2);
  edge(adj,0,1);
  edge(adj,1,3);
  edge(adj,2,0);
  edge(adj,2,3);
  edge(adj,2,4);
  cout<<"BFS traversal is"<<"  ";
  //call bfs funtion
  bfs(0,adj,visit);//1 is a starting point
  cout<<endl;
  //again initialise all node unvisited for dfs
  for(int i=0;i<5;i++){
    visit[i]=false;
  }
  cout<<"DFS traversal is"<<"  ";
  //call dfs function
  dfs(0,adj,visit);//1 is a starting point
}

Output

The output of our program is given below:

BFS traversal is  0 2 1 3 4
DFS traversal is  0 1 3 2 4

Important aspects:-

• Dfs takes less memory space, therefore, DFS is better than BFS.
• We can find the goal node fastly in DFS.
• For large network due to reoccurring of node, no guarantee to find the node in DFS but in BFS, we are definitely found the goal node.

Also, read:

Dijkstra’s shortest path algorithm in C++

Double Ended Queue in CPP – deque in C++