Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 46 ยท Uninformed Search

Breadth-First and Depth-First Search for AI

Apply breadth-first and depth-first search to AI problems: completeness, optimality, time and space, solving mazes and the 8-puzzle, and why memory is the real limit.

With the generic search skeleton in hand, the two simplest strategies are a one-word change apart. Take nodes from the front of the frontier (a queue) and you get breadth-first search. Take them from the back (a stack) and you get depth-first search. Both are called uninformed (or blind) because they know nothing about the problem except what actions, result and is_goal tell them. They have no sense of whether a state is "close" to the goal.

Even so, they behave very differently, and the differences are the key vocabulary of search: completeness, optimality, time and space. In this lesson you will watch both algorithms solve a maze and the 8-puzzle, measure what they do, and see the memory wall that makes breadth-first search impractical for big problems. If you want the plain-graph versions of these algorithms, see BFS and DFS in the DSA tutorial.

Breadth-first search (BFS) expands the shallowest unexpanded node. It finishes every node at depth 0, then every node at depth 1, then depth 2, and so on, like ripples spreading from the start.

  • Complete? Yes, if the branching factor is finite: the shallowest goal sits at some depth d, and BFS reaches depth d after expanding a finite number of nodes.
  • Optimal? Only when all steps cost the same (for example one per move). The shallowest goal is then the cheapest.
  • Time: about b^d nodes generated, where b is the branching factor and d the depth of the shallowest goal.
  • Space: also about b^d, since the whole frontier, one full layer, is kept in memory.

Depth-first search (DFS) expands the deepest node on the frontier. It dives down one branch until it hits a dead end or a goal, then backs up to the most recent unexplored alternative.

  • Complete? In graph search on a finite state space, yes. In tree search, no: loops make it run forever (see the previous lesson). In infinite spaces, it can wander down an endless branch.
  • Optimal? No. It returns the first goal it stumbles on, however long the path.
  • Time: b^m in the worst case, where m is the maximum depth, which can be far larger than d.
  • Space: for tree search, only b*m + 1 nodes: the current path plus the unexpanded siblings along it. This tiny memory footprint is DFS's great virtue.
BFS DFS (tree search) DFS (graph search)
Complete Yes (finite b) No Yes (finite space)
Optimal Yes, if steps cost the same No No
Time O(b^d) O(b^m) O(states)
Space O(b^d) O(b*m) O(states)
graph TD
    R["start"] --> A["1"]
    R --> B["2"]
    R --> C["3"]
    A --> A1["4"]
    A --> A2["5"]
    B --> B1["6"]
    B --> B2["7"]
    C --> C1["8"]

Numbers are the order in which nodes are first visited by breadth-first search (layer by layer). Depth-first search would instead go 1, 4, 5, then 2, 6, 7, then 3, 8, diving left first.

A maze with both algorithms

A maze is the cleanest place to see the difference. States are grid cells; actions move up, down, left or right unless a wall (#) is in the way. Every move costs 1, so BFS must return a shortest path. The code below uses the same loop for both strategies and only changes which end of the frontier it pops. It keeps a parent dictionary that doubles as the explored set and as the means of rebuilding the path.

Python BFS and DFS in a maze

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

BFS walks straight down the left edge: 4 steps, the shortest possible. DFS takes the last neighbor generated first, which is "right" here, so it runs the whole way across the top, around the wall and back along row 3, arriving after 22 steps. Both found a solution; only BFS found the best one.

Tip: DFS is sensitive to action order. Reverse the order of the four directions in neighbours and the path DFS finds changes completely. BFS always returns a path of the same, shortest length, though it may choose a different one among equals.

The 8-puzzle

Now the real test: a state space with 181,440 reachable states. We reuse the tuple encoding from Formulating Search Problems and solve one fixed scrambled board with both strategies.

Python Solving an 8-puzzle with BFS and DFS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two rows tell the story. BFS finds a solution of 18 moves, the shortest there is, after expanding 23,442 states. DFS "solves" the same puzzle too, but its answer is 54,404 moves long: a sequence you would never want to carry out. DFS dives so deep and so aimlessly that it only reaches the goal after wandering through most of the state space. For a puzzle, where the shortest solution is the whole point, that makes plain DFS a poor choice.

The memory wall

If BFS is complete and optimal, why not always use it? Because of the b^d term. Each extra level of depth multiplies the work by the branching factor, and the frontier has to be stored. The first experiment shows the layers of the 8-puzzle search above; the second extrapolates for a problem with branching factor 10 on a computer generating a million nodes per second and using 1 KB per node.

Python How fast do layers grow?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the bars: from depth to depth the layers grow by a factor of roughly 1.2 to 2. That is the 8-puzzle's gentle branching, with repeated states already removed, and it still reaches 11,132 states at depth 18. In the second table, a branching factor of 10 reaches 1.1 GB at depth 6 and terabytes by depth 10. The conclusion every AI course eventually draws: in breadth-first search, memory runs out long before time does. Waiting a day is fine; needing a terabyte is not.

Depth-first search avoids that wall in tree search, but only by giving up optimality and, often, termination. When you add an explored set to make DFS complete, its memory advantage disappears too, as the generated column of the 8-puzzle run shows: DFS stored 100,636 states, three times as many as BFS did. Is there a way to get BFS's guarantees with DFS's small memory? Yes, and the answer is iterative deepening, covered in a later lesson along with uniform-cost search for varying step costs.

When to use which

  • BFS: the shortest path in steps matters, the answer is probably shallow and memory is not a problem. Typical for small puzzles, shortest hops in a network, word ladders.
  • DFS: any solution will do, solutions are plentiful and deep, and memory is tight (tree search with a depth limit). Typical for constraint solving and puzzles like Sudoku, where it appears as backtracking.
  • Neither: when step costs vary (use uniform-cost search) or when you can estimate distance to the goal (use A*).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which data structure turns the generic search skeleton into breadth-first search?

    Removing the oldest node first means all nodes at depth k are expanded before any at depth k+1.
  2. 2. When is BFS guaranteed to return an optimal solution?

    BFS returns the shallowest goal. That is the cheapest only if cost is proportional to the number of steps.
  3. 3. What is the main practical weakness of breadth-first search?

    The whole frontier, a full layer of the tree, must be stored. Memory is exhausted before patience is.
  4. 4. In the 8-puzzle experiment, why was the DFS solution so long?

    DFS commits to a branch and follows it as deep as it can, so the first goal it finds is typically at the end of a very long path.
  5. 5. Which complexity describes depth-first TREE search memory?

    Tree search keeps only the current path and the unexpanded siblings along it. Graph search with an explored set loses this advantage.

Summary

  • BFS uses a queue, is complete, and is optimal when steps cost the same, but needs O(b^d) time and memory.
  • DFS uses a stack, needs little memory in tree search, but is not optimal and loops forever without repeated-state checking.
  • In the maze, BFS found the 4-step path; DFS found a 22-step one. In the 8-puzzle, BFS found 18 moves and DFS 54,404.
  • Memory, not time, is usually what stops breadth-first search.
  • Iterative deepening and uniform-cost search, next, repair the weaknesses of these two.

Next: Uniform-Cost, Depth-Limited and Iterative Deepening.