Imagine looking for a route through a maze. From each open square, try an available neighbor and keep following that path. When it ends, return to an earlier choice and try another route. This is depth-first search (DFS): it pursues one branch before exploring alternatives. section 2.2
A reusable Swift search separates the search procedure from the maze:
- Give dfs an initial state, a goal-test function, and a function that returns successor states. In the maze, successors are unblocked squares one step up, down, left, or right. section 2.2
- Put the initial node on a stack. Pop a node, test its state for the goal, then push unexplored successors. The last successor pushed is considered next, keeping the search on a deep branch. section 2.2
- Keep an explored set so routes that circle back do not repeatedly revisit states. Store each node’s parent so a found goal can be traced back to the start. section 2.2
Mark a route through a maze
Represent each square by a hashable row-and-column location. Start at (0, 0), test for the goal at (9, 9), and let the successor function reject walls and out-of-bounds moves. If dfs finds a goal node, follow its parent links to produce a path, then mark and print that path in the maze. section 2.2
Figure 2.4. In depth-first search, the search proceeds along a continuously deeper path until it hits a barrier and must backtrack to the last decision point.
The diagram shows why a blocked branch sends the search back to an earlier decision point rather than across all nearby squares. section 2.2
The stack distinguishes DFS from breadth-first search, which uses a queue to examine nearby states first. Both can serve as starting points for more elaborate searches; a path found by DFS is not presented as the shortest path. section 2.2 section 2.4
