Depth First Search Algorithm for Graph 

Depth First search algorithm is another important algorithm for Graph Traversal. Sometimes DFS, DFS-based Problem is asked in the GATE and UGC NET exams.

We have explained the Depth First Search Algorithm with examples here in this tutorial. After reading this tutorial, students will be able to solve the problem based on the depth-first search algorithm.

Depth First Search Algorithm and example-based Questions are asked in GATE (CS) and UGC NET exams. So GATE and UGC Net aspirants are suggested to prepare this topic very well.

So, let’s start with the introduction of Depth’s first search.

What is Depth First Search Algorithm ?

The Depth first search algorithm is a powerful technique of systematically traversing the edges of a given graph.

Every edge is traversed exactly once, and each vertex is visited at least once. It is called the Depth First Search (DFS) algorithm.

Process of Depth First Search Algorithm

The process of the Depth-first search algorithm is explained in the following three steps.

Step 1 – Start exploring a vertex.

Step 2 – While exploring that vertex, once we visit a new vertex, we’ll go on exploring it.

Step 3 – After exploring an adjacent vertex of the starting vertex, we’ll again come back to the starting vertex and visit and explore all the adjacent vertices of the same vertex.

Let’s try to understand DFS with a simple example-

In DFS, we’ll first visit vertex one and start exploring vertex 1. The adjacent vertices are 2, 5, 4. We’ll first visit 2 and explore 2.

The adjacent vertices of 2 are 3, 6 and 7. We’ll then visit and explore 3; but there is no adjacent vertex of 3.

Again, Vertex 6 and 7 also don’t have any adjacent vertex. We’ll visit vertex 6 and 7. After we’re done exploring vertex 2, we’ll start exploring vertex 1 again and visit sites 5 and 4.

Hence the result of DFS Traversal for the above graph will as shown in the sequence 1, 2, 3, 6, 7, 4, 5.

Depth First Search Example

In this section, we will understand the stepwise process of the depth-first search algorithm with the help of the depth-first search example.

Example – Let’s consider the graph given in the following figure. What will be the result of the Depth-first search on the above graph ?

Solution

In DFS, every time we visit a new vertex, we’ll explore that vertex as well.

First we’ll visit vertex 1 and explore it. i.e. visit 1’s adjacent vertex 2.

Once we visit 2 we’ll explore 2. 2 has adjacent vertices 4 and 5. But both vertices 4 and 5 don’t have any adjacent vertex. Hence vertices 4 and 5 are visited and explored.

Now we’ll go back and start exploring 1 once again and visit 3 and explore 3.

Adjacent vertices of 3 are 6, 7 and 9. First we’ll visit 6 and explore 6.

6 has 1 adjacent vertex; i.e. 8. We’ll now visit and explore 8.

7 is 8’s adjacent vertex. Hence we’ll visit 7 and explore 7. 3 is 7’s adjacent vertex, but 3 is already visited.

As we’re done visiting and exploring 6, we’ll explore 7. But 7 is already visited and explored.

Now we’ll visit and explore 9. 9 has 2 adjacent vertices, 1 and 3 and both are already visited.

As we are done exploring 3, we’ll now move to exploring 1 and try to visit 9, but 9 is already visited.

Hence all the vertices are visited and explored.

The above tree gives the DFS Spanning Tree. The dotted lines are called as back edges.

DFS traversal result is 1, 2, 4, 5, 3, 6, 8, 7, 9.

Conclusion and Summary

The stepwise process of the depth-first search algorithm for graph traversal is explained in this tutorial with examples.

I hope this Depth-first search algorithm tutorial will be beneficial for computer science students.

Previous Tutorial – Breadth First Search Algorithm for Graph