Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Graph Representation
2.1.
Depth First Search (DFS)
2.1.1.
Application of DFS
2.2.
Breadth-First Search (BFS)
2.2.1.
Applications of BFS
3.
DFS and BFS ON 2D GRID
4.
Frequently Asked Questions
4.1.
What is DFS?
4.2.
What is BFS?
4.3.
What are the applications of BFS?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Graph Traversal Techniques in DFS BFS

Author Sinki Kumari
1 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

People always try to find out a way to keep the order of their things. And to achieve this they keep on playing with different data structures until they find the best one. In this blog, we will be talking of one such Data Structure, namely a Graph.

Graph Traversals in DFS BFS

It is a non-linear data structure consisting of some nodes (or vertices) and edges (or links) between the nodes. In practical life; graphs are used to model many types of relations or networks of communication.

You can also read about the - hash function in data structure

Graph Representation

To represent a graph we can use either adjacency list of the adjacency matrix. Graphs can be directed or undirected. Undirected graphs have bi-directional edges which mean that if there exists an edge from node A to B then traversing either from A to B and vice versa is possible. Directed Graphs have directional edges which mean if there exists an edge from node A to B then vice versa movement is not allowed.
 

undirected graph

Undirected Graph

Directed graph

Directed Graph

Nodes in graph can be of two types root or leaf nodes. Root node is the start point in a graph and leaf node is basically a node that has no more child nodes. Leaf nodes do not have any outgoing edges.

Depth First Search (DFS)

 It is one of the main graph traversal algorithms. The main idea of DFS Algorithm traversal is to go as deep as possible and backtrack one we reach a vertex that has all its adjacent vertices already visited. Recursive implementation of the technique is very easy. We start at the source vertex and explores all its adjacent neighbours and further recursively call the function for the vertex if not visited. To keep track of nodes as visited or not we also keep a bool visited array initialised to false values. A snippet of the algorithm (in C++ for 1000 nodes) can be found below.

int nodes=1000;
vector<int> adj[nodes];
bool visited[nodes];
void dfs(int node)
{
     visited[node] = true;
    for(int child : adj[node])
    {
      if(vis[child] == false)
        {
        dfs(child);
        }
    }
    return ; 
}

As already mentioned this is a recursive implementation of DFS traversal. In iterative implementation we maintain a stack and push the adjacent child nodes of a node onto the stack and iterate while stack is not empty. Before pushing the child node we also check if the node is visited or not. Time Complexity of the recursive and iterative code is O (V+E), where V is no of vertices and E is the no of edges. Space Complexity is O (V) as we have used visited array.

void dfs(int node)
{
	stack<int> dfs_stack;
	dfs_stack.push(node);
	while(!dfs_stack.empty())
 	{
   		int curr_node = dfs_stack.top();
   		dfs_stack.pop();
  		if(!visited[curr_node])
   		{
   			cout<<curr_node<<" ";
   			visited[curr_node] = true;
   		}
		for(int child: adj[curr_node])
  		{
   			if(!visited[child])
    		{
     			dfs_stack.push(child);
    		}
  		}
 	}
	return;
}

DFS traversal techniques can be very useful while dealing with graph problems. Let me also mention that DFS will also return the shortest path in a tree (true only in case of trees as there exist only one path). A tree is a special case of a graph where the count of connected components is one and there are no cycles. The following image shows working of DFS. Here consider start node as node 1 and for keeping track of visited or not, consider node coloured in blue visited and node coloured in orange as not visited.

We start at node 1 and explore its neighbours 2 and 3.We can visit any node first. We now move to node 2 and explore its neighbours and once we reach a node with no more unvisited nodes we backtrack.

Application of DFS

  • Find a path from the source vertex to other vertices
     
  • Find the connected components in a graph
     
  • Topological Sorting
     
  • Find bridges and articulation points in a graph
     
  • Find LCA of two nodes in a graph
     
  • Find cycles in a directed and undirected graph
     

You can also read Detect cycle in an undirected graph here.

Breadth-First Search (BFS)

It is a traversing algorithm where you should start traversing from a start node and traverse the graphs layer-wise. In the case of a tree, this is the level order traversal. The above image depicts the working of BFS. As stated earlier, in BFS we first visit all the nodes of the current layer and then traverse nodes in the next layer. BFS implementation is also easier and we use a queue data structure to keep track of nodes in the current label. An important point about this traversal technique is that it traverses the shortest path (the path that contains the smallest number of edges) in an unweighted graph. To find the smallest path in a weighted graph we have Dijkstra’s Algorithm. Also in case, the weight is either 0 or 1 we can use 0/1 BFS. In 0/1 BFS we use a doubly ended queue.

A snippet of the iterative approach in BFS is shown below:

int nodes=1000;
vector<int> adj[nodes];
bool visited[nodes];
void bfs(int node)
{
	queue<int> q;
	q.push(node);
	visited[node] = true;
	while(!q.empty())
 	{
   		int curr = q.front():
   		q.pop();
		for(int child : adj[curr])
  		{
    		if(!visited[child])
    		{
       			q.push(child);
       			visited[child] = true;
     		}
   		}
   	}
 }
	return;
}

Here we push the source node on the queue and start exploring its non-visited child nodes level-wise and push the non-visited child nodes onto the queue. The time complexity of this technique is also O (V+E), where V is the number of vertices and E is the edges in the graph.

Applications of BFS

  • Finding the Shortest path in an unweighted graph
     
  • Find a solution to a game with the least number of moves. In such a scenario, each state of the game can be represented by a node, and state transitions as edges
     
  • Finding Connected Components in an unweighted graph
     
  • Level Order Traversal in Tree
     
  • Find the shortest paths in graphs with weights 0/1

Let us try applying the concept of BFS and DFS on 2D grids. In case of 2D grids we consider every cell as a node and edges are generally mentioned in the question but for in general sides are considered as edges and two cells are said to be connected if they share aside. In some cases, it is also mentioned that sides + corners are edges.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

DFS and BFS ON 2D GRID

Let us consider a 2D grid of some dimension and let us assume we are currently at cell (x, y). Now from the current cell we have 4 directions to move namely up, down, left and right (considering sides as edges only). Now in DFS we start exploring the adjacent vertices and mark these vertices as visited. So more or less in cases of 2D grids as well we apply the same logic as for graphs. Before we look at code for DFS, let us understand an important point as which cells are valid in our grid. Obviously, we need to care about boundary conditions. Hence those cells that are on the boundary and not visited are valid cells. Now let us look at the code snippet for the validity of a cell first and then for DFS.

int n,m;
int adj[n](s];
bool visited[n][m];
bool isvalid(int x , int y)
{
  if(x<0 || x>=n || y<0 || y>=m)
  {
     return false;
  }
 if(visited[x][y]==true)
 {
   return false;
 }
 return true;
}
void dfs(int x , int y)
{
	visited[x][yl=true;
  	if(valid(x-1,y))
 	{
    	dfs(x-1,y);//up
 	}
 	if(valid(x,y+1))
 	{
   		dfs(x,y+1); //right
 	}
 	if(valid(x+1,y))
 	{
   		dfs (x+1,y);//down
 	}
 	if(valid(x,y-1))
 	{
    	dfs(x,y-1);//left
 	}
}

A good practice of implementing DFS or BFS would be to keep an array for directions and then looping in all directions. Similar is the theory of BFS on Graphs and 2D Grids. Below is the snippet of direction vectors and BFS traversal using this direction vector.

int dx[4]={-1,0,1,0}; //direction array
int dy[4] = {0,1,0,-1};
bool  isvalid(int x, int y)
{
  if(x < 0 || x >=n || y < 0 || y >=m)
 { 
 	return false;
 }
 if(visited[x][y] == true)
 { 
 	return false;
 }
 return true;
}
 
void bfs(int x, int y)
{
  visited [x][y] = true;
  queue<pair<int, int>> q;
  q.push({x,y});
 while(!q.empty())
 {
   pait<int, int> curr = q.front();
   q.pop();
  for(int i=0; i < 4; i++)
   {
    int nextx=x+dx[i]; 
    int nexty=y+dy[i]; 
    if(isvalid(nextx,nexty))
      {
       q.push({nextx,nexty});
       visited[nextx][nexty]=true;
      }
   }
  }
}

BFS can be used to find the shortest path in a 2D grid and DFS can be used to find connected components in a 2D grid. In case of an edge is corners + sides (which will be mentioned in the question), then make sure to traverse in eight directions.

Frequently Asked Questions

What is DFS?

It is one of the main graph traversal algorithms. The main idea of DFS traversal is to go as deep as possible and backtrack one we reach a vertex that has all its adjacent vertices already visited. DFS traversal techniques can be very useful while dealing with graph problems.

What is BFS?

Breadth-First Search (BFS) is a traversing algorithm where you should start traversing from a start node and traverse the graphs layer-wise.

What are the applications of BFS?

There are various applications of the BFS algorithm, like finding the Shortest path in an unweighted graph, finding connected components in an unweighted graph, level order traversal in a Tree, finding the shortest paths in graphs with weights 0/1, and many more. 

Conclusion

In this blog, we have thoroughly discussed the graph traversal in DFS and BFS.  We further discussed the snippets of the code for DFS and BFS algorithms. We learned the algorithm and looked at the applications of DFS and BFS algorithms. 

Recommended problems -

 

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enrol in our coursesrefer to the mock test and problems look at the interview experiences and interview bundle for placement preparations.

Previous article
Dynamic Connectivity Problem
Next article
Breadth-First Search
Live masterclass