= Breadth-first search
{wiki}
= BFS
{c}
{synonym}
<Breadth-first search> is a <graph search> that explores successive layers of <graph distance> from a starting <vertex> $s$. Here the <graph> is an <undirected graph> on a <finite set> of <vertices>, and distance counts <edges>, with no differing <edge> weights. Mark $s$ as discovered, assign $d(s)=0$, and place it in a <FIFO queue>. Repeatedly remove the front <vertex> $u$ and scan its <adjacency list>. Whenever a <graph neighbour> $v$ is still undiscovered, mark it immediately, record $u$ as its <parent in a rooted tree> in the discovery <tree>, assign $d(v)=d(u)+1$, and enqueue $v$ at the rear. Marking on insertion ensures that another <edge> cannot enqueue the same <vertex> again. https://raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/BreadthFirstPaths.java[Sedgewick and Wayne, Algorithms: BreadthFirstPaths queue and discovery rule]{ref}
Use the same <undirected graph> as <depth-first search>, with <vertex set> $V=\{A,B,C,D,E,F,G\}$ and <edges>
$$
E=\{AB,AC,BD,BE,CE,CF,EG,FG\},
$$
where $XY$ denotes the unordered pair $\{X,Y\}$. Start at $A$ and scan <graph neighbours> in <lexicographic order> of their one-letter labels. The diagram's generator computes the following layers and the <parent in a rooted tree> assigned to each discovered <vertex>; the source is the <root of a tree> and has no <parent in a rooted tree>.
|| <Graph distance> from $A$
|| <Vertices> in discovery order
|| <Parent in a rooted tree> in the same order
| $0$
| $A$
| none
| $1$
| $B,C$
| $A,A$
| $2$
| $D,E,F$
| $B,B,C$
| $3$
| $G$
| $E$
\Image[/breadth-first-search-layers.png]
{title=<Breadth-first search>: <graph distance> layers and two ordered <FIFO queue> snapshots}
{description=Solid <edges> record first discovery; dashed <edges> are still present in the original <graph>. The <FIFO queue> contains $C,D,E$ after processing $B$ and $F,G$ after processing $E$, with its front on the left. Colors encode <graph distance> in the <graph> without <edge> weights.}
The discovery and removal orders both happen to be $A,B,C,D,E,F,G$. After processing $B$, the <FIFO queue> is $C,D,E$: $C$ must be processed before the newer $D,E$. Processing $C$ then skips the already discovered $E$ and enqueues $F$, giving $D,E,F$. Processing $D$ adds nothing. Processing $E$ discovers $G$, giving $F,G$; later $F$ sees $G$ already marked and leaves its <parent in a rooted tree> unchanged. The discovery <edges> are $AB,AC,BD,BE,CF,EG$, forming a <rooted tree> on all seven <vertices> even though the original <graph> contains <graph cycles>. The discovery <tree> contains six <edges>; it need not contain every examined <edge>.
First arrival is shortest because the <FIFO queue> keeps assigned distances in nondecreasing order, with entries from at most two consecutive layers. While processing distance $k$, newly discovered <vertices> receive distance $k+1$ and join the rear. If an undiscovered <vertex> had a shorter <graph path>, its preceding <vertex> on that <graph path> would lie in an earlier layer and would already have discovered it. Thus $d(v)$ is the minimum number of <edges> from $s$ to $v$. This is a <mathematical induction> over the layers, not an assumption about the drawing. Following the <parent in a rooted tree> backwards at each step gives $G,E,B,A$; reverse that <sequence> to obtain the three-<edge> <graph path> $A,B,E,G$. $A,C,F,G$ is another shortest <graph path>, but the specified <graph neighbour> order makes $E$ discover $G$ first. Changing that order can change the <parent in a rooted tree> without changing <graph distances>. https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/1208e162775f6f5cedfbb9f2b694ede0_MIT6_006F11_lec13.pdf[MIT 6.006, lecture 13: distance layers and shortest paths, pp. 4–6]{ref}
The shortest-route guarantee concerns the <shortest path problem> measured by <edge> count. It also minimizes total cost when every <edge> has the same positive cost. With unequal <edge> weights, first discovery need not minimize total cost; nonnegative costs can instead be handled by the <Dijkstra algorithm>. <Breadth-first search> is useful for minimum-hop routes and for finding all <vertices> within a specified <graph distance>. Its <FIFO queue> finishes an older layer before the next one, whereas <depth-first search> uses a <call stack> or explicit <LIFO stack> to pursue one branch immediately.
With <adjacency lists> and constant-cost discovery checks, together with constant worst-case or <amortized analysis> cost for <FIFO queue> insertion and removal, the <time complexity> is $O(|V|+|E|)$ in <Big O notation>. Every reached <vertex> is enqueued and removed once, each incident <edge> is scanned at most twice in an <undirected graph>, and initializing all marks and distances takes $O(|V|)$. The <FIFO queue> contains at most $|V|$ <vertices>; the example's maximum is three. Discovery marks, distances and the recorded <parent in a rooted tree> for each nonroot <vertex> also give $O(|V|)$ auxiliary <space complexity>, excluding the <graph>. An <array> that shifts every entry on front removal can lose the linear <time complexity>; the <FIFO queue> abstraction alone does not make removal constant-cost. Ordering the <adjacency lists> is a separate preprocessing cost.
A single start reaches only its <connected component of a graph>. Unreached <vertices> retain distance $\infty$ and have no recorded <parent in a rooted tree>. Restarting at each still-undiscovered <vertex>, while preserving all discovery marks, produces a <forest> covering the <graph>; each new <root of a tree> gets distance zero, so these distances refer to that <root of a tree>, not to the original $s$.
Back to article page
