Why keep a frontier?
Imagine a robot that can move along directed corridors. A map is useful only after we specify a start, the legal moves, and what makes a location a goal. If each move takes one minute, the fewest moves give the shortest trip. If corridors have different travel times, counting moves may select a slower trip. This difference is already enough to make the choice of search algorithm matter.
Definition 22.1.1
(State and search node)
A state records everything needed to decide the legal future moves and recognize a goal. If opening a door consumes a key, location alone is not a state: the pair (location, keys held) may be. A search node can instead describe a particular path to a state; distinct paths may arrive at the same state. Graph search identifies repeated states to avoid repeatedly exploring the same futures. That identification is valid only when equal state labels really have the same future possibilities and costs.
These notes develop finite graph versions of three basic methods. They prepare the ground for A*, where a heuristic changes the priority.
One problem, three frontier policies
Definition 22.1.2
(Search problem, frontier and solution)
Let be a finite directed graph, with start , goal set , and a fixed successor order for reproducible traces. A path's length is its number of edges. For uniform-cost search each edge additionally has a finite nonnegative cost ; the cost of a path is the sum of its edge costs. A solution is a path from to a goal, including the length-zero path if itself is a goal. A frontier stores discovered states whose outgoing edges have not yet been processed. Parent pointers reconstruct a path by following predecessors back to .
Definition 22.1.3
(Breadth-first search)
Breadth-first search (BFS) inserts into a first-in, first-out queue and marks it discovered. Repeatedly remove the front state ; if it is a goal, return its parent path. Otherwise, inspect its successors in order. For each undiscovered successor , mark it immediately, set its parent to , and enqueue it. If the queue empties, report failure. Marking on insertion prevents two parents from placing duplicate copies in the queue; a later path to that state is not needed for the fewest-edge objective.
Definition 22.1.4
(Depth-first search)
Depth-first search (DFS) can be implemented recursively: mark upon entry, test whether it is a goal, and visit each still-undiscovered successor in order, recording its parent before the call. Stop on the first goal, or report failure after the call from returns. The recursion stack stores the current path. Another explicit-stack implementation can visit a different order depending on when it marks states and inserts successors, so trace the actual implementation rather than relying on the name alone.
Definition 22.1.5
(Uniform-cost search)
Uniform-cost search (UCS) maintains a tentative cost , initially at and infinity elsewhere, and a minimum-priority queue containing . Remove an entry of least cost; ignore it if the state has already been settled or the entry differs from its current . Otherwise settle the state. If it is a goal, return its parent path and cost. For each outgoing edge, if , replace , set its parent to , and insert the improved entry. This permits stale queue entries instead of requiring a decrease-key operation. Equal-cost paths need not replace the recorded parent. A settled state is never improved under these hypotheses, as proved below.
Guarantees and proofs
Theorem 22.1.6
(BFS minimizes the number of edges)
On a finite directed graph, BFS returns a reachable goal of minimum path length, or correctly reports that no goal is reachable. It discovers each state at most once. Its time is with adjacency lists, and its auxiliary state and queue storage is .
Proof
(Queue order and shortest distances)
The queue starts with a depth-zero state. Whenever a depth- state is removed, new states enter at depth , behind entries already in the queue. Inductively the queue is ordered by nondecreasing recorded depth. Each discovered state has a parent path of its recorded depth. For this proof, consider the hypothetical full traversal that does not stop at goals and instead expands them normally. Prove by induction on shortest distance that every reachable state at distance is discovered at depth . The start gives . A shortest-path predecessor of at distance has distance and, by induction, is queued at that depth. It is removed before any depth- state, and then discovers unless was already discovered at depth at most . Since every discovered path is real, its depth cannot be less than the shortest distance . Thus the claim follows. The actual run agrees with this full traversal up to its first goal removal. If that goal had depth but another goal had smaller shortest distance, the full traversal would remove the latter first by queue order, a contradiction. Each state is inserted once and each outgoing edge is examined once, giving the bounds. Exhaustion means that every reachable state was processed, so failure is correct.
Proof X-ray
What the queue order buys
The proof has two parts. The invariant is that the queue is sorted by recorded depth, because each removed depth- state appends only depth- states behind older entries. The real idea is the induction on true distance: the predecessor of on a shortest path has distance , is therefore queued at depth , and is removed before any depth- state, so is discovered by depth and, since every recorded depth is a real path length, no earlier. Finiteness is used only for exhaustion, which makes a failure report correct. Nothing here uses edge costs, which is why BFS cannot see them.
Theorem 22.1.7
(UCS minimizes nonnegative path cost)
On a finite graph with finite nonnegative edge costs, the UCS procedure above settles every removed non-stale state at its minimum possible path cost. The first settled goal therefore has minimum cost among all reachable goals. If no goal is reachable, the procedure terminates and reports failure.
Proof
(The first wrongly settled state)
All finite tentative labels represent actual paths, so no label is below the true minimum. Suppose, for a contradiction, that is the first state settled with a label greater than its minimum. Choose a cheapest path to and let be its first unsettled state just before is settled. If , its label is zero. Otherwise its predecessor was settled correctly, and relaxing gave a label no greater than the cost of the path prefix to . This prefix costs at most the whole path because all remaining edges are nonnegative. Hence the queue contains a current entry for with priority at most the optimal cost of , strictly below the entry settling , a contradiction. The same frontier-prefix argument excludes a cheaper goal when the first goal is settled. There are finitely many states, and each is settled once; processing its finite outgoing edges creates finitely many queue entries. Thus the algorithm terminates, including with zero-cost edges.
Proof X-ray
Why nonnegative costs matter
The prefix of a cheapest path must cost no more than the whole path. A negative edge can reverse this inequality: an apparently expensive frontier prefix may lead to a cheap destination later. In that setting permanent settlement and stopping at the first goal can both fail.
Proposition 22.1.8
(Running time of uniform-cost search with stale entries)
With a binary heap and adjacency lists, the UCS procedure above runs in time for and uses space.
Proof
(Counting heap operations)
Each state is settled once, and settling it examines its outgoing edges once, so there are at most relaxations. Each successful relaxation inserts one entry, so at most entries are ever inserted and removed, and the heap never holds more than entries. Because , one heap operation costs . Removing an entry whose state is already settled costs one removal and no further work. Adding the bookkeeping gives the bound.
DFS also terminates on a finite graph when it marks states and each adjacency list is finite. If it returns failure, all reachable states have been visited. But the first goal it finds is governed by successor order, not by shortest length or cost. With adjacency lists, full graph DFS has time and storage including visited marks and recursion; it is misleading to describe graph DFS as using only path-depth memory while omitting visited marks. Without a visited set, a cyclic graph can cause an infinite walk even though it has finitely many states.
Worked examples: same graph, different answers
Worked example 22.1.9
(Breadth-first and depth-first search on one graph)
Take edges in the following listed order: costs , costs , costs , costs , and costs . There are no other edges. The paths are with three edges and cost , and with two edges and cost .
BFS removes , then , then . After these removals its queue is : was inserted by and by . Processing encounters an already discovered , so retains parent . BFS returns , the shortest in number of edges. It has no reason to compare the cost with .
Recursive DFS follows the first successor at each state, visiting , and returns that path. This particular order happens to produce the cheaper path; reversing the two successors of gives . No optimality conclusion follows from the lucky ordering.
Worked example 22.1.10
(Uniform-cost search with a tie and a late improvement)
UCS settles at , at , and then and at in either tie order. If is settled first, it inserts and then improves it to . If is settled first, it inserts and does not insert , since is not an improvement. The goal is settled at , returning . Stopping when is first discovered can return if is settled before .
Concept lensAlgorithmic
Uniform-cost search as breadth-first search on a subdivided graph
When every cost is a positive integer, replace each edge of cost by a chain of unit edges through new states. Path costs become edge counts, so layer of BFS on the subdivided graph contains exactly the original states whose minimum cost is , and UCS settles original states in the same order. In the example graph, and both lie in layer ; first appears in layer , through , while the route through reaches it only in layer . The description needs positive integer costs, since zero cost cannot be subdivided; the priority queue is the economical way to sweep the same layers.
Worked example 22.1.11
(A zero-cost cycle and an unreachable goal)
Let and both cost , and let cost . UCS settles at and inserts . It settles at ; relaxing is not an improvement because is false, and relaxing inserts . Settling at returns with cost . The zero-cost cycle causes no loop: each state is settled once and a replacement must be a strict improvement. If the edge is removed, the queue empties after and are settled, and the procedure correctly reports failure because no goal is reachable.
Counterexample mode
Fewest edges is not least cost
A direct edge of cost beats the two-edge route in edge count, but if both edges of the latter cost , it costs only . BFS is optimal for unit edge counts, or more generally equal positive edge costs, not for arbitrary nonnegative costs.
Common mistake
(Stopping at discovery instead of settlement)
In the example graph, is first discovered with label when is settled before . Returning at that moment gives cost , although costs and the label appears once is settled. For UCS the goal test belongs at the moment a state is removed from the queue and settled. (BFS may test at discovery, because every edge counts as one step.)
What a graph-search guarantee does not say
A finite graph may be exponentially larger than its compact problem description. For a tree with branching factor at most , the number of nodes through depth is at most ; that is a bound on an explicitly generated search tree, not automatically a bound in terms of the bit length of an arbitrary problem. Graph merging can save work when different paths share a valid state, but a poor state representation can merge situations with different futures and invalidate the result.
UCS is Dijkstra's algorithm stopped at a goal. For strictly positive equal edge costs, BFS and UCS agree on the optimal goal cost, although their tie choices may differ. If all edges cost zero, every reachable goal has cost zero, while BFS still chooses one of minimum edge count. A* extends UCS by ordering on ; its goal and reopening rules require their own hypotheses and are developed in the accompanying heuristic-search unit.
Practice
Quick check
(Use successor order , , , on unit-cost edges. Give the BFS removal order through the goal and its returned path. What path does recursive DFS return?)
Keep the queue explicitly and write it after every removal.
Solution · Answer
The queue evolves from to , then , then , and then . Removal order through the goal is . The parent of is , so the path is . Recursive DFS follows and stops there.
Quick check
(Edges are cost , cost , cost , cost , cost . Run UCS, giving settled labels and its returned path. Explain the stale entry for .)
Record every insertion with its priority, and note which entries are stale when they are removed.
Solution · Answer
Settle at and insert . Settle at , improve to , and insert . Settle at and improve to . The older entry is ignored because is already settled (and its priority differs from current ). Settle at . Its parent chain gives , with cost .
Quick check
(With edges cost , cost , and cost , show what happens if UCS stops when it settles . Which proof step fails?)
List the queue after is settled and ask which entry is removed first.
Solution · Answer
After , the queue contains and . The method settles and returns cost , but has cost . The prefix to costs , greater than the complete path's ; nonnegativity is exactly what made the proof's prefix bound valid. Negative cycles would introduce a further issue: an optimum might not exist at all.
Quick check
(A finite graph has a directed cycle and an edge . Explain why a recursive DFS that always visits before from can fail without a visited set. Explain why the marked version terminates and finds .)
Follow the recursion from and write down the sequence of calls.
Solution · Answer
Without marks, recursion alternates and never gets to the second successor of . With marks, the second encounter with is skipped, after which is visited. More generally, every state is entered at most once, and each finite successor list is eventually exhausted, so recursion terminates.