## 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.

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

1 2 3 4 5 6 7 8 9 10 |
Vertex1.VISIT <- TRUE PUSH Vertex1 while STACK NOT EMPTY Temp <- top of STACK if Undiscovered AdjacentVertex of Temp > 0 ConnectedVertex <- Undiscovered AdjacentVertex of Temp ConnectedVertex.VISIT <- TRUE PUSH ConnectedVertex else Temp <- POP from STACK |

## 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.

##### 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.

##### 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.

##### 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.

##### Step 4 :

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

##### Step 5 :

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

##### Step 6 :

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

##### 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.

##### 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.

##### Step 9 :

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

##### 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.

##### 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.

##### 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.

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
private List dfs(List<List> graph) { List visitedList = new ArrayList(); Stack tempStack = new Stack(); tempStack.push(1); visitedList.add(1); Integer temp = 1; while (!tempStack.isEmpty()) { temp = tempStack.peek(); boolean found = false; for(Integer vertex : graph.get(temp-1)){ if(!visitedList.contains(vertex)){ visitedList.add(vertex); tempStack.push(vertex); found = true; break; } } if(!found){ temp = tempStack.pop(); } } return visitedList; } |

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.