Depth First Search(DFS) Traversal in Data Structure

DFS stands for Depth First Search, is one of the graph traversal algorithms that uses Stack data structure. In DFS Traversal go as deep as possible of the graph and then backtrack once reached a vertex that has all its adjacent vertices already visited.

Depth First Search (DFS) algorithm traverses a graph in a depthward motion and uses a stack data structure to remember to get the next vertex to start a search, when a dead end occurs in any iteration.

DFS traversal for tree and graph is similar but the only difference is that a graph can have a cycle but the tree does not have any cycle. So in the graph we have additional array which keeps the record of visited array to protect from infinite loop and not visited again the visited node.

Steps to implement Depth First Traversal

Step 1 – Visit all adjacent unvisited vertex. Mark it as visited. Print it and Push it in a stack.

Step 2 − If no adjacent vertex is found, pop up a vertex from the stack.

Step 3 − Repeat Step 1 and Step 2 until the stack is empty.

Graph Traversal using DFS Technique

Initialize the stack

depth first traversal in data structure

Mark 12 as visited and push into stack. Now Explore any unvisited adjacent node from 12. In our example We have three nodes. We can pick any of them. Here we are going to pick 5.

dfs in data structure

Mark 5 as visited and put it onto the stack. Explore any unvisited adjacent node from 5. Both 12 and 25 are adjacent to 5 but we are concerned for unvisited nodes only.

depth first search graph traversal in data structure

Visit 25 and mark it as visited and put onto the stack. Here, we have 23 and 3 nodes, which are adjacent to 25 and both are unvisited.

depth first search graph traversal

We choose 3, mark it as visited and put onto the stack. Here 3 does not have any unvisited adjacent node. So, we pop 3 from the stack.

depth first search graph traversal in data structure

We check the stack top for return to the previous node and check if it has any unvisited nodes. Here, we find 25 to be on the top of the stack.

dfs searching technique

Only unvisited adjacent node is from D is 23 now. So we visit 23, mark it as visited and put it onto the stack.

depth first search graph traversal in data structure

Output of DFS Traversal will be : 3, 23, 25, 5, 12

Complexity Analysis

Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Space Complexity: O(V).
Since, an extra visited array is needed of size V.

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