Graph Traversal Techniques in DFS BFS

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.

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

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.