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.
- Take the empty queue and bool type array (visit) initialise with FALSE.
- Push the starting node in the queue and set the value TRUE for this node in visited array.
- Pop out the front node of the queue and print the node.
- Push the adjacent node of pop node in queue which are not visited. Set the value TRUE in visited array of adding node.
- Repeat step 3 and 4 until the queue becomes empty.
Now we will look on the algorithm for DFS.
- Take the empty stack and bool type array (visit) initialise with FALSE.
- Push the starting node in the stack and set the value TRUE for this node in visited array.
- Pop the top node from the stack and print that node.
- Push the adjacent node of pop node in the stack which is not visited. Set the value TRUE in visited array of adding node.
- 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++
Leave a Reply