Graph Traversal - Depth-First Search
Explore the Depth-First Search (DFS) algorithm in this lesson to understand recursive graph traversal using backtracking. Learn how to implement DFS with adjacency lists and stacks, mark visited nodes to prevent infinite loops, and analyze its time and space complexity. Gain practical skills to apply DFS in solving graph problems and decision trees.
We'll cover the following...
Depth-First Search approach
The Depth-First Search (DFS) algorithm is a recursive algorithm that uses the idea of Backtracking. It involves exhaustive searches of all the nodes by going ahead if possible, and if not, by backtracking. Here, the word backtrack means that when you are moving forward and there are no more nodes along the current path, you move backward on the same path to find nodes to traverse. All the nodes will be visited on the current path till all the un-visited nodes have been traversed after which the next path will be selected.
This recursive nature of Depth-First Search can be implemented using stacks. The basic idea is as follows:
- Pick a starting node and push all its adjacent nodes into a stack.
- Pop a node from the stack to select the next node to visit and push all its adjacent nodes into a stack.
- Repeat this process until the stack is empty. However, ensure that the nodes that are visited are marked. This will prevent you from visiting the same node more than once.