DFS is a recursive traversal algorithm for searching all the vertices of a graph or tree data structure. It starts from the first node of graph G and then goes to further vertices until the goal vertex is reached.
DFS uses stack as its backend data structure
edges that lead to an unvisited node are called discovery edges while the edges that lead to an already visited node are called block edges.
DFS procedure
DFS implementation categorizes the vertices in the graphs into two categories:
The major objective is to visit each node and keep marking them as “visited” without making any cycle.
Steps for DFS algorithms:
1. Start by pushing starting vertex of the graph into the stack
2. Pop the top item of the stack and add it to the visited list
3. Create the adjacency list for that vertex. Add the non-visited nodes in the list to the top of the stack
4. Keep repeating steps 2 and 3 until the stack is empty
Depth First Search Algorithm
Step 1: STATUS = 1 for each node in Graph G
Step 2: Push the starting node A in the stack. set its STATUS = 2
Step 3: Repeat Steps 4 and 5 until STACK is empty
Step 4: Pop the top node N from the stack. Process it and set its STATUS = 3
Step 5: Push all the neighbors of N with STATUS =1 into the stack and set their STATUS = 2
[END OF LOOP]
Step 6: stop
