Depth First Search (DFS) Traversal

Introduction to DFS

DFS is the complete other side of BFS. In DFS the search is carried out in a way by traveling to the depth starting from one node. Let's consider the below example.

In the above graph the DFS would be like this if we start from node 1.

1->2->4->5->3

This happens like this. Once the node 1 is considered it has neighbours 2 and 3. So we select one of them, say 2. Applying the same we have left with only one neighbour to node 2 which is 4, and then 5 to node 4. Again we get node 2 as a neighbour of node 2, but we ignore since we already considered not 2.

For this to implement we are using a Stack data structure, which has push and pop operations.

Lets see how we can model the procedure by using a stack (S).

Iteration 1:

S = 1

we remove 1 and push it's neighbours (1 is marked as discovered)

S = 3, 2

do the same with 2 (Discovering 2)

S = 3,5,4

remove 4 and push neighbours (Discovering 4)

S = 3,5,5

remove 5 and push 2? no because we have already discovered 2 (Discover 5)

S = 3,5

We have already discovered 5, so nothing happens 

S = 3

remove 3, Discovering 3

S = null

Procedure ends here.

Implementation of DFS

This can be represented as a Pseudo code

function DFS(vertex)

    Stack s

    s.push(vertex)

    while(s is not empty):

        vertex = s.pop()

        if(vertex is not discovered):

            mark vertex as discovered

            for(each neighbour n of vertex):

                s.push(n)

This can be implemented using JAVA as follows. Graph is initiated with the number of Nodes (node id starting from 0). Then edges are added (eg: 1,2 is an edge and so on). Finally the runDFS(v) method is called passing the node to start. In this method if a graph has two parts disconnected the other part will not be discovered as we move on with neighbouring nodes. In which case we can call the runDFS(n) method to each node n of the graph.