Uninformed search

You are dropped into a maze with no map. You cannot see the exit, you have no compass pointing the way, and no hint about which corridor is "warmer". All you can do is stand at a junction, notice which turns are available, take one, and repeat — remembering where you've been so you don't wander in circles. Somehow, from nothing but "here are my options", you must find the way out.

That is uninformed search (also called blind search): solving a problem by systematically exploring a space of states using no domain knowledge beyond the bare definition of the problem. The agent cannot tell whether one unexplored state is "closer" to the goal than another — it only knows the goal when it stands on it. That sounds hopeless, yet a handful of blind strategies are guaranteed to find a solution whenever one exists.

This page is about those strategies and, crucially, the one thing that separates them. They differ in a single design choice: the order in which they pull states out of a waiting list. Change that data structure and you change everything — memory, speed, whether the answer is even optimal. Get this frame right and later "informed" methods (like A*) are just this skeleton with a smarter ordering bolted on.

Formulating a search problem

Before you can search, you must say precisely what you are searching. A search problem is defined by five parts:

Initial state — where the agent starts (the maze entrance).
Actions — the set of moves legal in a given state (turn left, turn right, go straight).
Transition model — a function \text{Result}(s, a) giving the state you land in after doing action a in state s.
Goal test — a check that says whether a state is a goal (are we at the exit?).
Step cost / path cost — c(s, a, s') is the cost of one step; the path cost is the sum of step costs along a path. A solution is a path from the initial state to a goal; an optimal solution is one of least path cost.

The initial state, the actions, and the transition model together define a state space — the (possibly enormous) graph of every state reachable from the start. Uninformed search is the art of walking that graph without ever peeking at the map.

State graph vs. search tree

Here is the subtlety that trips up almost everyone. The state space is a graph: a state can be reached by many different paths, and paths can loop back on themselves. But a search algorithm unrolls that graph into a search tree, where the root is the initial state and each node is a distinct path the search has considered. Because the same state can sit at the end of many paths, one state in the graph can appear as many nodes in the tree.

If you don't guard against this, the tree balloons far larger than the graph — and if the graph has cycles, the tree becomes infinite. The cure is to keep two collections as you search:

the frontier (the "fringe") — states discovered but not yet expanded, waiting their turn;
the explored set (or reached set) — states already expanded, so we never process one twice.

Every strategy on this page shares this exact loop: pop a state off the frontier, test it for the goal, and if it isn't the goal, push its not-yet-seen neighbours onto the frontier. What makes the strategies behave completely differently is one thing only: which end of the frontier we pop from.

The frontier is the strategy

Change the frontier's discipline and you change the search:

Breadth-first search (BFS) uses a FIFO queue. The oldest state waiting is expanded first, so BFS fans out one whole level at a time — all states one step from the start, then all two steps away, and so on.
Depth-first search (DFS) uses a LIFO stack. The newest state is expanded first, so DFS plunges down one branch as far as it can before backing up.
Uniform-cost search (UCS) uses a priority queue ordered by path cost g(n). It always expands the cheapest-so-far state, which lets it cope with steps that cost different amounts.

BFS and DFS are the two you build on top of a plain graph traversal; UCS is the same skeleton with a cost-ordered frontier (it turns out to be Dijkstra's algorithm in disguise). Let's watch BFS peel the state space apart, level by level.

Watching BFS expand a search tree

Below is a small state space drawn as a search tree, root at the top. BFS expands states in level order: the root first, then everything one step down (left to right), then everything two steps down. The numbers show the order in which BFS visits each node — step through the reveal and watch it sweep across each level before descending.

Notice the shape of the work: to reach depth d, BFS must first hold every node above that depth in memory at once. With a branching factor of b, level k contains up to b^k nodes, so both the time and the space grow like O(b^d). That exponential frontier is BFS's blessing (it finds the shallowest goal) and its curse (it eats memory alive).

BFS vs. DFS, side by side

Talk is cheap — let's run both on the same tiny graph. The program below stores a graph as an adjacency list and searches from S to the goal G. BFS uses a queue (pop the front), DFS uses a stack (pop the back). Press Run and compare the visit orders: BFS spreads across each level, while DFS dives straight down a branch.

// Adjacency list: each state lists its neighbours. const graph: Record<string, string[]> = { S: ["A", "B"], A: ["C", "D"], B: ["D", "E"], C: [], D: ["G"], E: ["G"], G: [], }; function search(useStack: boolean): void { const frontier: string[] = ["S"]; const parent: Record<string, string | null> = { S: null }; const visited: string[] = []; while (frontier.length > 0) { const node = useStack ? frontier.pop()! : frontier.shift()!; // LIFO vs FIFO visited.push(node); if (node === "G") break; // goal test on expansion for (const next of graph[node]) { if (!(next in parent)) { // skip already-reached states parent[next] = node; frontier.push(next); } } } const path: string[] = []; for (let n: string | null = "G"; n !== null; n = parent[n]) path.unshift(n); console.log((useStack ? "DFS" : "BFS") + " visited: " + visited.join(" ")); console.log((useStack ? "DFS" : "BFS") + " path: " + path.join(" -> ")); } search(false); // BFS search(true); // DFS

Same graph, same start and goal — but the paths can differ. BFS is guaranteed to return a path with the fewest edges; DFS returns whatever path its plunge happened to find first, which may be needlessly long. Delete the if (!(next in parent)) guard and, on a graph with a cycle, DFS would loop forever — which is exactly the misconception in the next box.

Judging a search strategy: four criteria

We compare blind strategies on four standard yardsticks, phrased in terms of the branching factor b, the depth of the shallowest goal d, and the maximum depth of the space m:

Completeness — is it guaranteed to find a solution if one exists?
Optimality — does it find a least-cost solution?
Time complexity — how many states does it generate?
Space complexity — how many states must it hold in memory at once?

BFS — complete; optimal only when every step cost is equal (it finds the shallowest goal, not the cheapest); time and space both O(b^d).
DFS — not optimal, and not complete on infinite or looping spaces; but its great virtue is memory: it stores only the current branch, just O(b\,m) space.
UCS — complete and optimal for any non-negative step costs, because it always expands the least-path-cost state (this is Dijkstra's algorithm run as a search).

The trade is stark: BFS buys optimal-depth answers with punishing memory; DFS is memory-thrifty but can wander off forever and returns whatever it stumbles on; UCS pays with a priority queue to earn true cost-optimality.

The classic blunder is to drop the explored / reached set. Without it, your search stops distinguishing the compact state graph from the sprawling search tree: the same state gets re-expanded once for every path that reaches it, and the tree grows exponentially larger than it needs to be. Worse, if the state graph contains a cycle, a tree-style search with no memory of where it has been will loop through that cycle forever — never terminating even though a solution sits nearby.

This bites DFS hardest, and it's the reason DFS is not complete on infinite or looping spaces: it can plunge down an endless branch and never come back. Always track reached states (or, at minimum, avoid revisiting states already on the current path). And keep the two failings of DFS straight in your head: it is neither optimal (it returns the first path it finds, however long) nor, without cycle-checking, complete.

Because BFS's real enemy is memory, not time. People often assume the O(b^d) time is what kills it — but a computer that generates a million nodes a second will chew through a lot of time. The genuine wall is space: BFS must keep the entire frontier in memory, roughly b^d states, all at once, so it can expand them in level order.

With branching factor b = 10 and depth d = 12, that's on the order of a trillion stored states — terabytes of RAM — long before you run out of patience. This is precisely why DFS's modest O(b\,m) footprint is so prized, and why a clever hybrid, iterative deepening, exists: it runs DFS to depth 1, then 2, then 3…, getting BFS's shallow-goal guarantee with DFS's tiny memory, re-expanding the upper levels as a cheap price to pay.