The idea of breadth-first search is to explore a graph from a start vertex s one
distance at a time. BFS first visits every neighbour of s, then every neighbour of
those neighbours, and so on, so it finishes all vertices at one distance from s before
it moves on to the next. Because vertices are reached in order of distance, the first time BFS
reaches a vertex it has found a shortest path to it: the path with the fewest edges.
BFS uses a queue to get this order. The queue holds vertices that have been found but whose
neighbours have not been looked at yet, and it starts with just s. In each step, BFS takes the vertex at the
front of the queue, call it u, and looks at each of its neighbours. A neighbour that
has not been found before is one edge further from s than u, so BFS
records its distance and adds it to the back of the queue. New vertices always join at the back,
so a vertex leaves the queue before any vertex with a larger distance. The
search ends when the queue is empty: every vertex reachable from s has been added to
the queue once and taken out once.
For each vertex u, BFS records two values. d[u] is the distance from
s, the number of edges on a shortest path. It starts at ∞, which also means
"not found yet", and it is set when u is first seen as a neighbour, not later when
u leaves the queue. prev[u] is the vertex BFS came from when it found
u. Following prev
back from any vertex to s gives a shortest path, and together these links form the
BFS tree.
Cost: O(V + E). Each vertex enters the queue at most once (only while its d is ∞), and each adjacency list is scanned once, when its vertex leaves the queue.
qEvery reachable vertex except s has exactly
one prev, so the prev links form a tree. The path from s down
this tree to any vertex is a shortest path in the graph.
Both searches run on the same graph from the same source. The code is the same except for one line: BFS takes vertices from the front of a queue, DFS from the top of a stack.
| 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 |
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 from any vertex not yet discovered:
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" plays the role of d[v] = ∞. 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".