Let us say for above graph figure 1(a)
Source node - 1
Destination node – 5
1. On pressing any key it starts with source node that is Node 1. It is shown by another round of red colour on particular node as shown in figure 1(b)
Figure 1(b)
2.Node 1 has two child or neighbour nodes Node 4 and Node 5. As DFS go for the first most child, it explores Node 4 as shown in figure 1(c)
Figure 1(c)
3.Further Node 4 behaves as parent node. It looks for child node. Node 2 and Node 3 are child or neighbour nodes of Node 4. Again as Node 2 is first most child, it is explored next as shown in figure 1(d)
Figure 1(d)
4. After Node 2, Node 3 explores as the first most child as shown in figure 1(e) but node 3 has no unvisited child nodes so here search gets stuck to move more deeply. So here concept of backtracking works.
Figure 1(e)
Backtracking is a concept according to which if search reaches to dead end or leaf node, search goes back to previous explored node or can say previous execution.
In above example, Search gets stuck at Node 3. Node 3 does not have any unvisited child node so Node 3 is known as dead end. Here using backtracking concept search goes back to Parent node of Node 3 that is Node 2. But both child nodes Node 3 and Node 4 of Node 2 are already visited. It backtracks to Node 4 as this is parent node of Node 2 and further back tracks to Node 1. Node 1 has two child nodes Node 4 and Node 5. Node 4 is already visited; next Node 5 is explored as shown in figure 1(f)
Figure 1(f)
Node 5 is destination node. Hence Depth First Search completed.