Depth First Search

Suppose the graph (figure 1(a)) is drawn showing interconnected cities. It is a two way graph. A person can move in any direction like from vertex 2 to vertex 4 or vertex 4 to vertex 2. An edge tells distance between two connected cities. Different search algorithms use the different strategies to find the path from source node to destination node.

Figure 1(a)

DEPTH FIRST SEARCH

Depth First Search algorithm goes deeper and deeper at each step. For a search tree, starting from source node taken as parent node explore the first most child node ( nodes are in increasing order, node having lowest number is taken as first most child) then further first most child of child node and soon till when destination node is found or it get stuck with no child node further.

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.