4.3.2 Combining Stack and Graph to perform DFS
Computational Structures
Depth-First Search (DFS) is a fundamental algorithm used to explore or traverse through a graph or tree structure. It uses a stack data structure to keep track of the vertices or nodes that need to be visited. This method is particularly useful when we need to explore as far as possible along a branch before backtracking, making it ideal for situations where deep exploration is required.
Example: Consider the graph shown in Figure 4.13, as a tree with numeric nodes:
In this graph:
- Node 1 is the root.
- Nodes 2, 3, and 4 are children of node 1.
- Nodes 5 and 6 are children of node 2.
- Node 7 is a child of node 3.
- Nodes 8 and 9 are children of node 4.
Here's how the DFS algorithm uses a stack to traverse this graph:
- Start with an empty stack and push the root node (1) onto the stack.