Starting from one vertex s: which vertices can I reach, and what is the
fewest number of edges to each one?
Visit vertices in order of their distance from s:
s itselfsAll vertices at distance k are found before any vertex at distance k + 1, so the first time a vertex is found, the distance recorded for it is its shortest distance. A FIFO queue gives exactly this order: vertices leave the queue in the order they were added.
ucolor[u]: white = not found yet,
gray = found, waiting in the queue,
black = done, all its neighbours checked.d[u]: the number of edges on a shortest path from s;
∞ if u is never reached.prev[u]: the vertex we came from when u was first found
(its predecessor, written u.π in CLRS). Following prev
back to s gives a shortest path; together the prev links form the
BFS tree.Cost: O(V + E). Each vertex enters the queue at most once (only while it is white), and each adjacency list is scanned once, when its vertex leaves the queue.
q.popleft() vs stack.pop()This DFS marks a vertex visited when it is popped, not when it is pushed. A vertex can sit on the stack several times (once for each visited neighbour that pushed it); only its first pop counts, and later copies are skipped. Marking on push instead would give a different order that is not a true depth-first order.
Pushing the neighbours in reverse makes the first neighbour come off the stack first, so
this iterative version visits vertices in the same order as the recursive DFS in CLRS.
The recursive version also records two timestamps per vertex: u.d when it is
discovered and u.f when it finishes (all its descendants done). For this graph,
starting from the source and then any vertex left white:
| BFS | DFS | |
|---|---|---|
| Container | queue - deque.popleft() | stack - list.pop() |
| Order | by distance from the source: all of distance k before any of k + 1 | as deep as possible along one branch, then back up |
| prev links give | shortest paths (fewest edges) | a spanning tree whose paths can be longer than necessary |
| Cost | O(V + E) | O(V + E) |
| Typical uses | shortest path in an unweighted graph, "within k hops" queries, level-by-level processing | cycle detection, topological sort, strongly connected components, maze generation |
Each problem below is the same bfs() on a different graph. Often the graph is never
stored: the neighbours of a vertex are worked out when the vertex is popped. Then
d starts empty and "v not in d" does the job of "white". Each step
below is one pop: u leaves the queue and all its new neighbours join it.
Vertices are 4-letter words; two words share an edge when they differ in exactly one letter. BFS from the start word gives the fewest one-letter changes to reach the end word.
Vertices are the 64 squares; an edge joins two squares a knight can jump between in one move. BFS from the start square gives the fewest moves to every square.
A farmer must take a wolf, a goat and a cabbage across a river in a boat that holds the farmer and one more. Left alone, the wolf eats the goat and the goat eats the cabbage. Vertices are the safe states (which bank each one is on; the boat is always with the farmer); edges are single crossings. BFS from "all on the left" gives the fewest crossings. Try it by hand on the wolf-goat-cabbage page.
Vertices are land cells; an edge joins two land cells that touch on a side. Each BFS run finds every cell of one island, so the number of islands is the number of runs needed to see all the land. Click a cell to switch it between land and water.
Vertices are the open cells of a map (dark cells are walls); edges join cells that touch on a side. Lettered cells are hospitals. Putting every hospital in the queue at d = 0 before the loop gives, in one pass, each cell's distance to its nearest hospital and which one it is. Click an open cell to add or remove a hospital.
Vertices are people; an edge means two people are friends. BFS from one person, stopped at distance 2, gives their friends (d = 1) and friends of friends who are not yet friends (d = 2), the usual "people you may know" list. Click a person to start from them.
1945 - Konrad Zuse. BFS and its use for finding connected components appear in Zuse's rejected Ph.D. thesis on the Plankalkül programming language; it was not published until 1972.
1959 - Edward F. Moore. Moore reinvents BFS to find the shortest path out of a maze ("The shortest path through a maze").
1961 - C. Y. Lee. Lee develops it into a wire-routing algorithm for circuit boards, still known as the Lee algorithm.
DFS. A version of depth-first search was studied in the 19th century by Charles Pierre Trémaux as a method for solving mazes. In the 1970s John Hopcroft and Robert Tarjan built linear-time graph algorithms on DFS (biconnected components, planarity testing); their work on algorithms and data structures earned them the 1986 Turing Award.
See Breadth-first search and Depth-first search on Wikipedia, and CLRS (Introduction to Algorithms), chapter "Elementary Graph Algorithms", whose example graph is the first preset above.