---
title: "Depth-first search and comparing searches"
course: "AI101 · AI, explained"
unit: "Building with rules and search"
lesson: 18 of 36
source: https://open.maestrocollege.edu/ai-explained/depth-first-search-and-comparing-searches
publisher: Maestro College
---

# Depth-first search and comparing searches

Lesson 18 of 36 in **AI, explained** (AI101), unit "Building with rules and search". An open lesson from Maestro College.

## What the learner will be able to do
- Build a depth-first search that keeps its frontier in a stack and records visited states.
- Compare the paths, the number of states explored and the largest frontier size of depth-first and breadth-first search on the same problem.
- Choose between breadth-first and depth-first search for a given problem based on whether a shortest path is needed and how many states the frontier may hold.

## Teaching notes
STARTING STATE: search.py with neighbors() and bfs(). IN THIS LESSON: the learner writes dfs(maze) with a Python list as a stack and the same visited set, parent dictionary and return shape, then prints both searches' path lengths, explored counts and largest frontiers side by side; if the paths tie on this maze, have them reverse the neighbor order or type in a small maze to see that depth-first search gives no shortest-path guarantee. END STATE: a valid path and its 'dfs | maze' line in RESULTS.md, committed as 'Add depth-first search'.

## Course teaching approach
- Start from a real-world problem, then introduce the concept as the solution.
- Keep it true beginner level, hands-on, a little gamified. The learner should feel they are winning.
- Balance explanation, demonstration and practice. No copy-paste exercises: give small story-based tasks.
- End with one fun closed question about the topic.

## How to use this document
You are acting as a tutor for a learner on Maestro Open. Teach from this document, one small step at a time. Ask the learner to try things, wait for their answer, then give feedback. Keep it beginner-friendly. If the lesson involves code or spreadsheets and you cannot run them, ask the learner to try it on their own computer and paste the result back. Do not award grades, credit or certificates.

## When the lesson is done
The lesson is complete only when the learner has shown they can do every outcome listed above. Check each one with a small task or question; if an answer is wrong, explain and let them try again before moving on.
When every outcome is covered:
1. Say clearly: "Lesson 18 complete: Depth-first search and comparing searches."
2. Give a two-line recap of what they learned.
3. Name the next lesson, "Challenge: finding where rules break" (lesson 19 of 36), and give the learner its link: https://open.maestrocollege.edu/ai-explained/challenge-finding-where-rules-break.md. Tell them to paste that page into this chat, or fetch it yourself if you can open links, then start it the same way. Do not start teaching the next lesson's topic until the learner has it.

Previous lesson: Breadth-first search
Next lesson: Challenge: finding where rules break