# 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:**

- Initiate by keeping any one of the graph’s vertices on top of a stack.
- Put the top item of the stack in the visited list.
- Make a list of that adjacent vertex’s node. Add the node which is not visited on the top of the stack.
- 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**

- Put any one of the graph’s vertices at the back end of the queue.
- Put the front item of the queue in the visited list.
- Created a list of adjacent nodes. Those nodes that are not visited will be placed at the back of the queue.
- 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