Depth First Search Algorithm
Depth First Search (DFS) is a graph traversal algorithm.
When DFS is implemented on a graph, a source node is chosen and from this, we traverse to nodes as ‘deep into’ the graph as possible.
Consider the graph below:
Suppose we choose Node ‘3’ to be the source node. From ‘3’ we traverse to ‘5’.
Next, we can traverse ‘1’, but for that we will be required to go back to ‘3’.
We don’t do that.
As long as there is an edge coming out of our current node, we keep moving forward.
From ‘5’ we can go to ‘2’ or ‘4’. Let’s go to ‘4’.
The traversal till now is:
3 →5 →4
From ‘4’, we move forward to ‘6’ and from ‘6’ to ‘8’.
3 →5 →4 →6 →8
We see that there is no edge coming out of ‘8’. So we retrace our path one edge backwards.
We move back to ‘6’ and check if there is any other edge(not traversed before) coming out of it. There isn’t any.
So we move back one more edge, retracing our path. We move to ‘4’.
We check if there is any other edge coming out of ‘4’. There isn’t any.
We move back one more edge and reach ‘5’.
We see that there is an edge coming out of ‘5’ which has not yet been traversed. We move along that edge and reach ‘2’.
3 →5 →4 →6 →8 →2
Now, from ‘2’ there is only one outgoing edge which reaches ‘6’ and ‘6’ has already been visited. So, we backtrack and reach ‘5’.
From ‘5’ there is no unvisited outgoing edge. So we backtrack and reach ‘3’.
From ‘3’, there is one edge outgoing that has not been visited before, we traverse this edge and reach ‘1’.
3 →5 →4 →6 →8 →2 →1
From ‘1’, we move to ‘7’.
3 →5 →4 →6 →8 →2 →1 →7
From ‘7’ we can move to ‘2’ or ‘8’. But both are already visited. So we backtrack and reach ‘1’. No remaining untraversed edge from ‘1’, we backtrack again and reach ‘3’. There is no untraversed edge from ‘3’.
We reached to our starting node with no untraversed edge remaining, that means, we have traversed the entire graph using DFS.
In code, a stack data structure is used to implement DFS on graphs.
A stack follows Last In First Out (LIFO).
Let us see how a stack can be used in DFS. We will also keep a ‘list of visited nodes’ to avoid traversing already traversed nodes.
Let source node = ‘3’.
Push it into the stack.
Stack: 3
Store the value of the top of the stack in a variable x and pop it.
x=3
Stack: Empty
3 →
Push all the immediate neighbors of x into the stack.
Stack: 1,5
Store the top of the stack in x and pop it.
x=5
Stack: 1
3 →5 →
Push all the immediate neighbors of x into the stack.
Stack: 1, 2,4
Store the top of the stack in x and pop it.
x=4
Stack: 1,2
3 →5 →4 →
Push all the immediate neighbors of x into the stack.
Stack: 1,2,6
Store the top of the stack in x and pop it.
x=6
Stack: 1,2
3 →5 →4 →6 →
Push all the immediate neighbors of x into the stack .
Stack: 1,2,8
Store the top of the stack in x and pop it.
x=8
Stack:1,2
3 →5→4 →6 →8 →
Push all the immediate neighbors of x into the stack. There are no edges coming out of ‘8’. So we move to the next step.
Store the top and pop.
x=2
Stack: 1
3 →5→4 →6 →8 →2
Push all the immediate neighbors of x. ‘2’ has only one outgoing edge. To ‘6’, which has already been traversed. We hence move to the next step.
Store the top and pop.
x=1;
Stack: Empty
3 →5→4 →6 →8 →2 →1
Push all the immediate unvisited neighbors of x.
Stack: 7
Store the top and pop.
x=7
Stack: Empty
3 →5 →4 →6 →8 →2 →1 →7
Push all the immediate neighbors of x. There are no unvisited neighbors of ‘7’ left. No further action will take place.
Stack is now empty, which means we have traversed the entire graph using DFS.
Pseudo Code:
