Graph search: the first thing AI could actually do — and still useful today.
History 10 min Intermediate April 26, 2026
Your phone finds the fastest route through millions of streets in milliseconds. How? It searches a graph. This technique — modeling problems as graphs and searching them systematically — is where artificial intelligence began.
In this article, you will learn the two fundamental search strategies that powered the earliest AI programs: Breadth-First Search (BFS) and Depth-First Search (DFS). You already know graphs as data structures — now they become tools for AI.
State Space — Every Problem Is a Graph
Any problem with a defined start, a goal, and allowed actions can be represented as a graph. This abstraction is the central idea of classical AI: whether chess, route planning, or puzzles — everything becomes the same mathematical structure.
State Space
AnalogyDefinition
Think of a maze: every intersection is a state, every corridor is a transition, the entrance is the start state, and the exit is the goal. Finding your way through the maze — that is graph search.
Analogy:
Think of a maze: every intersection is a state, every corridor is a transition, the entrance is the start state, and the exit is the goal. Finding your way through the maze — that is graph search.
Definition:
A state space is a graph that models a problem: nodes represent states (e.g., a particular puzzle configuration), edges represent actions (e.g., sliding a tile), and the solution is a path from the start state to the goal state. The graph is generated on-the-fly, not stored in full.
Where the maze analogy breaks: a maze is two-dimensional and manageable. Chess has approximately 10⁴⁴ legal positions — a maze the size of a galaxy.
Take the 8-Puzzle (3×3 sliding puzzle): the start state is a random arrangement of tiles 1-8, the goal is the ordered sequence. Each move slides one tile into the empty space. The state space has exactly 181,440 reachable states (9!/2).
181,440
8-Puzzle Reachable states (9!/2)
~10⁴⁴
Chess Legal positions
~10¹⁷⁰
Go Legal positions
Misconception: The algorithm builds the entire graph in memory
No. States are generated on-the-fly — the algorithm computes successor states only when it needs them. Storing the entire graph for chess (10⁴⁴ positions) would require more storage than exists on Earth.
Breadth-First Search (BFS) — Level by Level
Breadth-First Search explores the state space layer by layer: first all neighbors of the start node, then their neighbors, and so on. It uses a queue (FIFO — First In, First Out). To see how this search works in practice, let's switch from the maze to a different picture: imagine searching for a friend in a building. You check all rooms on your floor first (level 0), then go up one floor (level 1) and check all rooms there. You are guaranteed to find your friend on the nearest floor. Where the analogy breaks: a building has few floors with a constant number of rooms. In a state space, each level has exponentially more nodes than the previous one.
BFS Step by Step
1
We start at A and mark it as visited.
2
We look at A. It has two neighbors: B and C. Both join the queue.
3
Next up is B. B has neighbors D and E — both join the queue.
4
Now C is next. C has one neighbor: F. F joins the queue.
5
D is checked (dead end). E is checked (F already known).
6
F comes up — that's our goal! Path: A → C → F, just 2 edges. That's the shortest path.
BFS is complete (always finds a solution if one exists) and optimal (finds the shortest path by edge count). The cost: time and space complexity O(b^d) — exponential. In the following example, we use a small graph: A is the start node. From A, edges lead to B and C. From B, edges lead to D and E. From C, an edge leads to F. From E, an edge also leads to F. The goal is F.
Misconception: BFS is always the best choice
BFS requires O(b^d) memory — exponential in solution depth. For chess with branching factor b=35 and depth d=80, BFS would need to examine roughly 35⁸⁰ nodes. That is more operations than atoms in the observable universe (10⁸⁰). BFS is optimal but often physically impossible.
Depth-First Search (DFS) — As Deep as Possible
Depth-First Search takes the opposite approach: it follows one path as deep as possible before backtracking and trying alternatives. It uses a stack (LIFO — Last In, First Out) or recursion. Imagine navigating a maze by always turning left. When you hit a dead end, you go back to the last intersection and try right. You will find the exit — but probably not via the shortest route. Where the analogy breaks: "always turn left" works in physical mazes (walls prevent cycles). In graphs, DFS can loop endlessly without a visited set.
DFS Step by Step
1
We start at A. A is not the goal. We pick the first neighbor: B.
2
B is not the goal. On to B's first neighbor: D.
3
D is not the goal and has no neighbors — dead end! Back to B.
4
B has another neighbor: E. Let's try that.
5
E is not the goal. E has one neighbor: F.
6
F is the goal — found it! Path: A → B → E → F, that's 3 edges.
DFS is not complete (can get stuck in cycles) and not optimal (finds a path, not the shortest). But DFS needs only O(b·m) memory — dramatically less than BFS.
Misconception: DFS finds the shortest path
No. DFS finds the first path it stumbles upon — and which path that is depends on the order of neighbors. In the example, DFS found [A, B, E, F] with 3 edges, while BFS found the shorter [A, C, F] with 2 edges.
BFS vs. DFS — The Trade-Off
There is no "better" algorithm — the choice depends on the problem.
BFS (Breadth-First Search)
Data structure: Queue (FIFO). Finds shortest path: Yes. Complete: Yes. Memory: O(b^d) — exponential. Best for: Small state spaces, shortest path required.
DFS (Depth-First Search)
Data structure: Stack (LIFO). Finds shortest path: No. Complete: No (without cycle detection). Memory: O(b·m) — linear. Best for: Deep state spaces, limited memory, existence check.
BFS wins for small state spaces when the shortest path is needed. DFS wins for deep state spaces, limited memory, or when any path will do.
Interactive: Compare BFS and DFS Live
You have learned about BFS and DFS in theory. Now you can try both algorithms on the same graph. Switch between BFS and DFS, step through the execution — and observe how differently they traverse the graph.
Queue (FIFO)
A
Visited
none yet
Click "Step" to start the breadth-first search.
Unvisited
In queue/stack
Current
Visited
Goal found
Why Blind Search Hits a Wall
In his seminal 1950 paper "Programming a Computer for Playing Chess," Claude Shannon distinguished two strategies: Type A (brute force — examine all moves to a fixed depth) and Type B (selective — favor promising moves). Type A corresponds to BFS; Type B points toward heuristic search.
The exponential explosion makes blind search impossible for real problems: the 8-Puzzle has 181,440 states (solvable), the 15-Puzzle has ~1.05 × 10¹³, a Rubik's Cube ~4.3 × 10¹⁹, chess ~10⁴⁴, and Go ~2.08 × 10¹⁷⁰.
A clever compromise: run depth-first search repeatedly, going one level deeper each time. This combines the guarantees of breadth-first search with the memory efficiency of depth-first search.
Blind search (BFS/DFS) cannot solve real-world AI problems alone. The next article introduces heuristics — intelligent shortcuts that make search practical.
Key Takeaways
Any problem with defined states, transitions, and goals can be modeled as a state space — making it searchable by algorithms.
BFS guarantees the shortest path but consumes exponential memory. DFS uses minimal memory but may find long detours or loop forever.
Blind search works for small state spaces but is physically impossible for complex problems like chess — this is why AI needs heuristics (next article).
Quiz: Graph Search
Question 1 / 6
Not completed
What does a "state" represent in a state space?
1. What does a "state" represent in a state space?
☐ A) A variable in the program code
☐ B) A specific configuration of the problem (e.g., a particular puzzle arrangement)
☐ C) The amount of memory the algorithm uses
☐ D) The number of edges in the graph
2. Which data structure does BFS use, and what property does this guarantee?
☐ A) Stack (LIFO) — guarantees the deepest path is found first
☐ B) Queue (FIFO) — guarantees the shortest path by edge count
☐ C) Array — guarantees all states are visited alphabetically
☐ D) Tree — guarantees the solution with the fewest nodes
3. A navigation app must find the route with the fewest road segments between two cities. The road network has 500 intersections. Which algorithm is appropriate?
☐ A) DFS — because it uses less memory and roads go deep
☐ B) BFS — because it guarantees the shortest path by edge count and 500 nodes are feasible
☐ C) Neither — 500 intersections are too many for any search algorithm
☐ D) DFS — because it always finds the optimal route
4. A robot must check if ANY path exists through a maze with 1,000 levels. Memory is limited to 1 MB. Which algorithm is more appropriate?
☐ A) BFS — because it is complete and always finds a solution
☐ B) DFS — because it needs only O(b·m) memory and is the better choice for deep state spaces with limited memory
☐ C) BFS — because it is faster than DFS at 1,000 levels
☐ D) Neither — mazes with 1,000 levels are unsolvable
5. You trace DFS and BFS on the same graph from A to F. BFS returns [A, C, F] (2 edges), DFS returns [A, B, E, F] (3 edges). Why did DFS find a longer path?
☐ A) DFS made an error
☐ B) DFS explored the left branch (A→B) deeply before ever considering the right branch (A→C), finding F via a longer route first
☐ C) DFS does not use a visited set and visited F twice
☐ D) The graph has weighted edges and DFS optimizes for weight, not edge count
6. Chess has approximately 10⁴⁴ legal positions with a branching factor of about 35. A student claims: "We just need a faster computer to run BFS on chess." Evaluate this claim.
☐ A) Correct — Moore's Law will eventually make BFS fast enough for chess
☐ B) Incorrect — 35⁸⁰ exceeds the number of atoms in the observable universe; no physically possible computer can run BFS on chess
☐ C) Correct — BFS only needs to search a small fraction of the state space
☐ D) Incorrect — but only because chess is unsolvable, not because of computation limits
Answer Key: 1) B · 2) B · 3) B · 4) B · 5) B · 6) B
Comprehension Check
Take an everyday problem like your commute to work: what would the states be, what the transitions, and what the start and goal?
Describe the difference between BFS and DFS using the A-to-F graph example: why do they find different paths?
Why can no computer in the world solve chess with pure breadth-first search — and what is needed instead?