Graph Search — The Beginnings

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.

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).

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 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.

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 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.

BFS vs. DFS — The Trade-Off

There is no "better" algorithm — the choice depends on the problem.

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.