3.7.3.2 Depth-First Search (DFS)
Algorithms and Problem Solving
Depth-First Search (DFS) is another graph traversal algorithm that explores as far down a branch as possible before backtracking to explore other branches. It uses a stack to manage the nodes to be explored.
Process:
- Start from the root node and push it onto the stack.
- Pop a node, process it, and push all its unvisited neighbors onto the stack.
- Repeat the process until the stack is empty.
Example: DFS can be used in solving puzzles like mazes, where the algorithm explores one possible path to the end, and if it hits a dead end, it backtracks and tries another path.
Complexity: The time complexity of DFS is O(V+E), similar to BFS. However, DFS is more memory-efficient for deep graphs, while BFS is more suited for shallow graphs.
Figure 3.9 compares the BFS and DFS algorithms, showing how BFS explores a graph level by level, while DFS explores as far as possible down each branch before backtracking.