Breadth-first search is an efficient graph traversal algorithm that finds,
for the given source vertex \(s\),
all the vertices that are reachable from \(s\), and
a shortest simple path from \(s\) to each reachable vertex.
The idea is to start from the source vertex \(s\) and
traverse its outgoing edges.
The neighbor vertices that have not yet been visited
are put in a first-in-first-out (FIFO) queue.
Each vertex is taken out of the queue and its neighbors are then visited in the same manner and put at the end of the queue if not yet visited.
At each point, a vertex is colored
white if it has not yet been found reachable from \(s\),
gray if it has been found reachable from \(s\) but
not all its outgoing edges have been traversed, and
black if it has been found reachable from \(s\) and
all its outgoing edges have been traversed.
In addition, each vertex \(t\) is associated with
a distance attribute that tells the length of the shortest path from \(s\) to \(t\), and
a predecessor attribute that stores the neighbor from which a shortest path
from the source to it was produced.
In pseudocode, we can express the algorithm as follows.
Breadth-first-search(\(G\), \(s\)):
for each vertex \(\Vtx \in \Verts \setminus \Set{s}\): // Initialize colors, distances and predecessors
\(\GColor{\Vtx} \Asgn \GWhite\)
\(\GDist{\Vtx} \Asgn \infty\)
\(\GPred{\Vtx} \Asgn \GNil\)
\(Q \Asgn \emptyset\) // \(Q\) is a FIFO-queue
\(\GColor{s} \Asgn \GGray\) // Initialize the source vertex \(s\) to gray
\(\GDist{s} \Asgn 0\)
\(\GPred{s} \Asgn \GNil\)
enqueue(\(Q\), \(s\))
while \(Q\) is not empty:
\(u \Asgn {}\)dequeue(\(Q\)) // Take the earliest gray vertex from the queue
for each \(\Vtx\) with \(\Set{u,\Vtx} \in \Edges\): // Traverse each edge from it
if \(\GColor{\Vtx} = \GWhite\): // The neighbour \(\Vtx\) has not yet been visited?
\(\GColor{\Vtx} \Asgn \GGray\) // Color it gray
\(\GDist{\Vtx} \Asgn \GDist{u}+1\) // Store the distance
\(\GPred{\Vtx} \Asgn u\) // And the path from the source
enqueue(\(Q\), \(\Vtx\)) // Put it at the end of the queue
\(\GColor{u} \Def \GBlack\) // All edges from \(u\) traversed
Example
The animation below shows breadth-first search on a graph with two connected components.
The source vertex is \(a\).
Each annotated graph in the animation shows the colors, distances, and
predecessor edges in the beginning and end of each while loop and
at the end of the algorithm (the last graph).
The neighbors are added in the queue in the alphabetic order.
For directed graphs one just replaces the line
“for each \(\Vtx\) with \(\Set{u,\Vtx} \in \Edges\)”
in the pseudocode with
“for each \(\Vtx\) with \(\Tuple{u,\Vtx} \in \Edges\)”.
Example: Breadth-first search on a directed graph
The animation below shows a breadth-first search on
a directed graph when the source vertex is \(a\).
Again, the neighbors are added in the queue in the alphabetic order.
At the end of the algorithm, a vertex
is black if it is reachable from the source vertex, and
is white if it is not reachable from the source.
Furthermore, for each black vertex
the distance attribute gives the length of the shortest path(s) from the source to the vertex, and
following the predecessor edges produces a shortest path to the source vertex.
Let us perform an analysis for the worst-case running time of the algorithm.
We observe the following facts:
Each vertex is added in the queue once.
Each edge is considered
twice for undirected graphs; once for each end-point when it turns from gray to black, and
once for directed graphs when the source end-point turns from gray to black.
Enqueue and dequeue are constant time operations for queues.
As a consequence,
the algorithm runs in time \(\Oh{\Card{\Verts}+\Card{\Edges}}\).
By performing breadth-first search from a white vertex until there are no white vertices left,
one can find all the connected components of an undirected graph.
Thus the connected components can be found in time
\(\Theta(\Card{\Verts}+\Card{\Edges})\).