Depth-First Traversal Algorithm

Depth first Search or Depth first traversal is a recursive algorithm for searching all the vertices of a graph or tree data structure.

The depth-first traversal or DFS algorithm traverses or explores data structures, such as trees and graphs. The algorithm starts at the root node (in the case of a graph, you can use any random node as the root node) and examines each branch as far as possible before backtracking.

To implement DFS traversal, you need to utilize a stack data structure with a maximum size equal to the total number of vertices in the graph.

The DFS algorithm works as follows:

Step 1: Start by putting any one of the graph's vertices on top of a stack.

Step 2: Take the top item of the stack and add it to the visited list.

Step 3 : Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the top of the stack.

Step 4: Keep repeating steps 2 and 3 until the stack is empty.

Application of DFS Algorithm

1. For finding the path
2. To test if the graph is bipartite
3. For finding the strongly connected components of a graph
4. For detecting cycles in a graph

Below depicts a traversal example based on Depth First Search Algorithm









Stack Empty , all nodes traversed.