Depth-first search (DFS) traverses a tree or graph by committing to one path and exploring as deeply as possible before backtracking to try another. It is like exploring a maze: keep walking forward until reaching a dead end, then return to the last intersection. Unlike breadth-first search, which expands evenly by depth, DFS dives down one branch first. section 2.11 section 2.8
A stack gives DFS its characteristic order:
- Place the root or starting node on a last-in, first-out (LIFO) stack. section 2.12
- Pop a node, skip it if already visited, otherwise mark it visited. section 2.12
- If the node is the goal, reconstruct the route by following parent references back to the root. section 2.12
- Otherwise, assign the current node as each neighbor’s parent and push those neighbors onto the stack. section 2.12
- Continue until the stack is empty; then report that no path was found. section 2.12
Maze traversal
In a maze, DFS adds the current position to the stack, repeatedly pops the next position, records it as visited, checks whether it contains the goal marker '*', and pushes its neighbors. Because recently added positions are processed first, the search reaches leaf-node depth before backtracking. A visited list prevents unnecessary repeated processing, while parent links preserve the route to the goal. section 2.12 section 2.8
def run_dfs(maze_game, current_point):
visited_points = [] #A
stack = [current_point] #A
while stack: #B
next_point = stack.pop() #C
if not is_in_visited_points(next_point,
➥visited_points): #D
visited_points.append(next_point) #D
if maze_game
➥.get_current_point_value(next_point)
➥== '*': #E
return next_point #E
else:
neighbors =
➥maze_game.get_neighbors(next_point) #F
for neighbor in neighbors: #F
neighbor.set_parent(next_point) #F
stack.append(neighbor) #F
return 'No path to the goal found.'
A compact Python implementation shows the stack loop, visited-point check, goal test, neighbor expansion, and parent assignment. section 2.12
DFS is useful when a problem can be represented as a tree or graph and a deep exploration order is appropriate. It is an uninformed search: it uses only the problem representation, not domain guidance. Cycle-handling rules matter; forbidding previously occupied maze blocks can prevent endless loops but may exclude solutions that require revisiting a block. section 2.13 section 2.8
