Depth First Traversal

Introduction

This is the second post in the Graph Traversals – Online Classes.

I Recommend you to look at the first post Breadth First Traversal as it contains more explanation and details and I will keep this post smaller just around the depth first concept.

Depth First Traversal

The Idea
In this traversal, we choose a start vertex and keep moving forward along the length of the graph until there is no undiscovered vertex in that path. Once reaching a dead end, we back track to all the visited vertices and check if we have any vertex which has an adjacent undiscovered vertex.

We keep performing the above procedure till there is any undiscovered vertex. Here is a diagrammatic representation for the same. The color change from one vertex two another in the below graph represents a possible alternate path.
DFS

In the above graph the possible paths are:

  • Path – 1, 2, 3, 4
  • Path – 1 ,7, 6, 5, 9
  • Path – 1 ,7, 8
Describing the Algorithm

Step 1: Visit the first vertex, you can choose any vertex as the first vertex (if not explicitly mentioned). And push it to the Stack.
Step 2: Look at the undiscovered adjacent vertices of the top element of the stack and visit one of them (in any particular order).
Step 3: Repeat Step 2 till there is no undiscovered vertex left.
Step 4: Pop the element from the top of the Stack and Repeat Step 2, 3 and 4 till the stack is not empty.

Pseudo Code

Explanation

Let us choose the start vertex as vertex 1. Mark it visited and push it to the stack. All the undiscovered vertices are colored white.
Depth First Traversal

Step 1 :

Look at the top of the stack (Vertex 1) and find any of its undiscovered adjacent vertex (Vertex 2). Mark it visited and push it on the stack.
Depth First Traversal

Step 2 :

Look at the top of the stack (Vertex 2) and find any of its undiscovered adjacent vertex (Vertex 3). Mark it visited and push it on the stack.
Depth First Traversal

Step 3 :

Look at the top of the stack (Vertex 3) and find any of its undiscovered adjacent vertex (Vertex 4). Mark it visited and push it on the stack.
Depth First Traversal

Step 4 :

Look at the top of the stack (Vertex 4) and find any of its undiscovered adjacent vertex (None). Pop from the Stack.
Depth First Traversal

Step 5 :

Look at the top of the stack (Vertex 3) and find any of its undiscovered adjacent vertex (None). Pop from the Stack.
Depth First Traversal

Step 6 :

Look at the top of the stack (Vertex 2) and find any of its undiscovered adjacent vertex (None). Pop from the Stack.
Depth First Traversal

Step 7 :

Look at the top of the stack (Vertex 1) and find any of its undiscovered adjacent vertex (Vertex 7). Mark it visited and push it on the stack.
Depth First Traversal

Step 8 :

Look at the top of the stack (Vertex 7) and find any of its undiscovered adjacent vertex (Vertex 8). Mark it visited and push it on the stack.
Depth First Traversal

Step 9 :

Look at the top of the stack (Vertex 8) and find any of its undiscovered adjacent vertex (None). Pop from the Stack.
Depth First Traversal

Step 10 :

Look at the top of the stack (Vertex 7) and find any of its undiscovered adjacent vertex (Vertex 6). Mark it visited and push it on the stack.
Depth First Traversal

Step 11 :

Look at the top of the stack (Vertex 6) and find any of its undiscovered adjacent vertex (Vertex 5). Mark it visited and push it on the stack.
Depth First Traversal

Step 12 :

Look at the top of the stack (Vertex 5) and find any of its undiscovered adjacent vertex (Vertex 9). Mark it visited and push it on the stack.
Depth First Traversal

Following the above procedure, we will end up popping from Stack and at the end the Stack will be empty. There is no change in any of the paths as we already visited all the vertices.

Source Code – Depth First Traversal

To download the complete code please visit techieme github repository

Analysis of the Algorithm

The running time of the algorithm would be O(|V|+|E|) by the same definition as for Breadth First Search. We at most visit all the vertices and edges not more than once.

The auxiliary space required is same as the BFS. A stack and a list to maintain the visited vertices. So it would be proportional to |V|.

Applications of Depth First Traversal

.

  • Finding all the paths from root to leaf in a n-ary tree.
  • Finding all the connected components of the graph.
  • Solving Path finding in Mazes.
  • Topological Sorting.

Don’t forget to subscribe to TechieMe to get updates on latest posts.