Unweighted Graphs: Breadth-First Search

Implementation of breadth-first search

In the simplest special case of the shortest path problem, all edges have weight 1, and the length of a path is just the number of edges. This special case can be solved by a species of our generic graph-traversal algorithm called breadth-first search. Breadth-first search is often attributed to Edward Moore, who described it in 1957 (as “Algorithm A”) as the first published method to find the shortest path through a maze. Especially in the context of VLSI wiring and robot path planning, breadth-first search is sometimes attributed to Chin Yang Lee, who described several applications of Moore’s “Algorithm A” (with proper credit to Moore) in 1961. However, in 1945, more than a decade before Moore considered mazes, Konrad Zuse described an implementation of breadth-first search as a method to count and label the components of a disconnected graph.

Breadth-first search maintains a first-in-first-out queue of vertices, which initially contains only the source vertex s. At each iteration, the algorithm pulls a vertex $u$ from the front of the queue and examines each of its outgoing edges $u\rightarrow v$. Whenever the algorithm discovers an outgoing tense edge $u\rightarrow v$, it relaxes that edge and pushes vertex $v$ onto the queue. The algorithm ends when the queue becomes empty.

$\underline{BFS(s)} \\ \hspace{0.4cm} InitSSSP(s) \\ \hspace{0.4cm} Push(s) \\ \hspace{0.4cm} while\space the\space queue\space is\space not\space empty \\ \hspace{1cm} u←Pull() \\ \hspace{1cm} for\space all\space edges\space u\rightarrow v \\ \hspace{1.7cm} if\space dist(v) > dist(u) + 1 \hspace{1cm} {\color{Red} \left< \left<\space if\space u\rightarrow v \space is\space tense \space \right > \right >} \\ \hspace{2.3cm} dist(v) ← dist(u) + 1 \\ \hspace{2.3cm} pred(v) ← u \hspace{2.1cm} {\color{Red} \left< \left<\space relax\space u\rightarrow v \space\right > \right >} \\ \hspace{2.3cm} Push(v)$

Explanation

• Line 6: Here, we have a constant integer variable named INF with a value of 1 billion.

• Line 7: Here, we have a constant integer variable named MAXN with a value of 100005.

• Line 13: The InitSSSP function initializes the distance, predecessor, and visited arrays for all nodes except the source node s.

• Lines 13–23: The code first sets all the dist values to INF (infinity), all the pred values to -1, and all the visited values to false for every node in the graph. Then, it sets the dist value of the source node s to 0, as the distance from s to itself is 0.

• Lines 25–29: The code pushes s onto the back of q, and it sets the boolean flag visited[s] to true. The reference to q is passed by non-const reference, which means that any changes made to q inside the function will affect the caller’s copy of q.

• Lines 31–55: The BFS function performs a level-by-level traversal of the graph, updating the shortest path and predecessor arrays along the way, until all vertices have been explored.

Modifications of breadth-first search

Breadth-first search is somewhat easier to analyze if we break its execution into phases by introducing an imaginary token. Before we pull any vertices, we push the token into the queue. The current phase ends when we pull the token out of the queue; we begin the next phase when we push the token into the queue again. Thus, the first phase consists entirely of scanning the source vertex $s$. The algorithm ends when the queue contains only the token. The modified algorithm is shown below, and the illustration shows an example of this algorithm in action. Let us emphasize that these modifications are merely a convenience for analysis; with or without the token, the algorithm pushes and pulls vertices in the same order, scans edges in the same order, and outputs exactly the same distances and predecessors.