Depth First Search Algorithm

A DFS algorithm, as the name implies, is used to search deeper in the graph, whenever possible. The edges are explored, out of the most recently discovered vertex v that still has unexplored edges leaving it. When all of v's edges have been explored, the search backtracks to explore edges leaving the vertex from which v was discovered. This process continues until we have discovered all the vertices that are reachable from the source vertex. DFS uses stack structure to maintain the order in which the vertices are to be processed.

Algorithm:

Step 1: Initialize all nodes to ready state (status = 1)

Step 2: Push the starting node in stack and change its status to the waiting state (status = 2)

Step 3: Repeat step 4 and 5 until stack is empty

Step 4: pop the top node n of stack. Process n and change the status of n to the processed state (status = 3)

Step 5: Push on to the stack, all the neighbor of n that are in ready state (status = 1), and change their status to the waiting state (status = 2) [End of the step 3 loop]

Step 6: exit

Output: