Explain Depth First Search and Breadth First Search in Data Structure | Data Structure tutorial

Depth First Search and Breadth First Search in Data Structure

In this article, you will understand the Depth First Search and Breadth First Search algorithm in data structure

Depth First Search in Data Structure

It is a repetitive algorithm that helps in searching all the vertices of a graph or tree data structure. Traversal means visiting all the nodes of the trees and graphs one by one. 

Algorithm

The implementation of DFS keeps the vertex of the graph in one of two categories:

• Visited
• Not Visited

The main aim of the depth-first search algorithm is to mark each vertex as visited while avoiding cycling.

The workflow of the DFS algorithm is:

1. Initiate by keeping any one of the graph’s vertices on top of a stack. 
2. Put the top item of the stack in the visited list. 
3. Make a list of that adjacent vertex’s node. Add the node which is not visited on the top of the stack. 
4. Keep executing the 2 and 3 steps again and again until the stack is empty.

The complexity of Depth First Search

The time complexity of the DFS is O(V+E), where V is the number of nodes and E is the number of edges. 

The space complexity of the algorithm is O(V). 

Applications of Depth First Search

• Used in finding the path. 
• Used in detecting cycles in a graph
• Used in strongly connected components of a graph. 

Breadth-First Search in Data Structure

Breadth First Search is a repetitive algorithm for finding out all the vertices of a graph and tree data Structure. Traversal means visiting all the nodes of the graph and tree. 

Algorithm

The implementation of DFS keeps the vertex of the graph in one of two categories:

• Visited
• Not Visited

The main aim of the depth-first search algorithm is to mark each vertex as visited while avoiding cycling.

The workflow of the Breadth First Search algorithm

1. Put any one of the graph’s vertices at the back end of the queue.
2. Put the front item of the queue in the visited list. 
3. Created a list of adjacent nodes. Those nodes that are not visited will be placed at the back of the queue.
4. Keep executing the 2 and 3 steps again and again until the queue is empty.

The complexity of Breadth-First Search

The time complexity is 0(V+E), where v represents the number of nodes and E is the number of edges.

The space complexity is 0(V).

Applications of Breadth-first Search

• It is used for GPS Navigation.
• Used in Minimum Spanning tree
• Used in detecting the cycle in an undirected graph.
• Used in Pathfinding algorithm