|
|
< Day Day Up > |
|
Breadth-first search is one of the simplest algorithms for searching a graph and the archetype for many important graph algorithms. Prim's minimum-spanning-tree algorithm (Section 23.2) and Dijkstra's single-source shortest-paths algorithm (Section 24.3) use ideas similar to those in breadth-first search.
Given a graph G = (V, E) and a distinguished source vertex s, breadth-first search systematically explores the edges of G to "discover" every vertex that is reachable from s. It computes the distance (smallest number of edges) from s to each reachable vertex. It also produces a "breadth-first tree" with root s that contains all reachable vertices. For any vertex v reachable from s, the path in the breadth-first tree from s to v corresponds to a "shortest path" from s to v in G, that is, a path containing the smallest number of edges. The algorithm works on both directed and undirected graphs.
Breadth-first search is so named because it expands the frontier between discovered and undiscovered vertices uniformly across the breadth of the frontier. That is, the algorithm discovers all vertices at distance k from s before discovering any vertices at distance k + 1.
To keep track of progress, breadth-first search colors each vertex white, gray, or black. All vertices start out white and may later become gray and then black. A vertex is discovered the first time it is encountered during the search, at which time it becomes nonwhite. Gray and black vertices, therefore, have been discovered, but breadth-first search distinguishes between them to ensure that the search proceeds in a breadth-first manner. If (u, v) ∈ E and vertex u is black, then vertex v is either gray or black; that is, all vertices adjacent to black vertices have been discovered. Gray vertices may have some adjacent white vertices; they represent the frontier between discovered and undiscovered vertices.
Breadth-first search constructs a breadth-first tree, initially containing only its root, which is the source vertex s. Whenever a white vertex v is discovered in the course of scanning the adjacency list of an already discovered vertex u, the vertex v and the edge (u, v) are added to the tree. We say that u is the predecessor or parent of v in the breadth-first tree. Since a vertex is discovered at most once, it has at most one parent. Ancestor and descendant relationships in the breadth-first tree are defined relative to the root s as usual: if u is on a path in the tree from the root s to vertex v, then u is an ancestor of v and v is a descendant of u.
The breadth-first-search procedure BFS below assumes that the input graph G = (V, E) is represented using adjacency lists. It maintains several additional data structures with each vertex in the graph. The color of each vertex u ∈ V is stored in the variable color[u], and the predecessor of u is stored in the variable π[u]. If u has no predecessor (for example, if u = s or u has not been discovered), then π[u] = NIL. The distance from the source s to vertex u computed by the algorithm is stored in d[u]. The algorithm also uses a first-in, first-out queue Q (see Section 10.1) to manage the set of gray vertices.
BFS(G, s) 1 for each vertex u ∈ V [G] - {s} 2 do color[u] ← WHITE 3 d[u] ← ∞ 4 π[u] ← NIL 5 color[s] ← GRAY 6 d[s] ← 0 7 π[s] ← NIL 8 Q ← Ø 9 ENQUEUE(Q, s) 10 while Q ≠ Ø 11 do u ← DEQUEUE(Q) 12 for each v ∈ Adj[u] 13 do if color[v] = WHITE 14 then color[v] ← GRAY 15 d[v] ← d[u] + 1 16 π[v] ← u 17 ENQUEUE(Q, v) 18 color[u] ← BLACK
Figure 22.3 illustrates the progress of BFS on a sample graph.
The procedure BFS works as follows. Lines 1-4 paint every vertex white, set d[u] to be infinity for each vertex u, and set the parent of every vertex to be NIL.Line 5 paints the source vertex s gray, since it is considered to be discovered when the procedure begins. Line 6 initializes d[s] to 0, and line 7 sets the predecessor of the source to be NIL. Lines 8-9 initialize Q to the queue containing just the vertex s.
The while loop of lines 10-18 iterates as long as there remain gray vertices, which are discovered vertices that have not yet had their adjacency lists fully examined. This while loop maintains the following invariant:
At the test in line 10, the queue Q consists of the set of gray vertices.
Although we won't use this loop invariant to prove correctness, it is easy to see that it holds prior to the first iteration and that each iteration of the loop maintains the invariant. Prior to the first iteration, the only gray vertex, and the only vertex in Q, is the source vertex s. Line 11 determines the gray vertex u at the head of the queue Q and removes it from Q. The for loop of lines 12-17 considers each vertex v in the adjacency list of u. If v is white, then it has not yet been discovered, and the algorithm discovers it by executing lines 14-17. It is first grayed, and its distance d[v] is set to d[u]+1. Then, u is recorded as its parent. Finally, it is placed at the tail of the queue Q. When all the vertices on u's adjacency list have been examined, u is blackened in lines 11-18. The loop invariant is maintained because whenever a vertex is painted gray (in line 14) it is also enqueued (in line 17), and whenever a vertex is dequeued (in line 11) it is also painted black (in line 18).
The results of breadth-first search may depend upon the order in which the neighbors of a given vertex are visited in line 12: the breadth-first tree may vary, but the distances d computed by the algorithm will not. (See Exercise 22.2-4.)
Before proving the various properties of breadth-first search, we take on the somewhat easier job of analyzing its running time on an input graph G = (V, E). We use aggregate analysis, as we saw in Section 17.1. After initialization, no vertex is ever whitened, and thus the test in line 13 ensures that each vertex is enqueued at most once, and hence dequeued at most once. The operations of enqueuing and dequeuing take O(1) time, so the total time devoted to queue operations is O(V). Because the adjacency list of each vertex is scanned only when the vertex is dequeued, each adjacency list is scanned at most once. Since the sum of the lengths of all the adjacency lists is Θ(E), the total time spent in scanning adjacency lists is O(E). The overhead for initialization is O(V), and thus the total running time of BFS is O(V + E). Thus, breadth-first search runs in time linear in the size of the adjacency-list representation of G.
At the beginning of this section, we claimed that breadth-first search finds the distance to each reachable vertex in a graph G = (V, E) from a given source vertex s ∈ V. Define the shortest-path distance δ(s, v) from s to v as the minimum number of edges in any path from vertex s to vertex v; if there is no path from s to v, then δ(s, v) = ∞. A path of length δ(s, v) from s to v is said to be a shortest path[1] from s to v. Before showing that breadth-first search actually computes shortest-path distances, we investigate an important property of shortest-path distances.
 |
Let G = (V, E) be a directed or undirected graph, and let s ∈ V be an arbitrary vertex. Then, for any edge (u, v) ∈ E,
δ(s, v) ≤ δ(s, u) + 1.
Proof If u is reachable from s, then so is v. In this case, the shortest path from s to v cannot be longer than the shortest path from s to u followed by the edge (u, v), and thus the inequality holds. If u is not reachable from s, then δ(s, u) = ∞, and the inequality holds.
We want to show that BFS properly computes d[v] = δ(s, v) for each vertex v ∈ V. We first show that d[v] bounds δ(s, v) from above.
|
|
Let G = (V, E) be a directed or undirected graph, and suppose that BFS is run on G from a given source vertex s ∈ V. Then upon termination, for each vertex v ∈ V, the value d[v] computed by BFS satisfies d[v] ≥ δ(s, v).
Proof We use induction on the number of ENQUEUE operations. Our inductive hypothesis is that d[v] ≥ δ(s, v) for all v ∈ V.
The basis of the induction is the situation immediately after s is enqueued in line 9 of BFS. The inductive hypothesis holds here, because d[s] = 0 = δ(s, s) and d[v] = ∞ ≥ δ(s, v) for all v ∈ V - {s}.
For the inductive step, consider a white vertex v that is discovered during the search from a vertex u. The inductive hypothesis implies that d[u] ≥ δ(s, u). From the assignment performed by line 15 and from Lemma 22.1, we obtain
|
d[v] |
= |
d[u] + 1 |
|
≥ |
δ(s, u) + 1 |
|
|
≥ |
δ(s, v). |
Vertex v is then enqueued, and it is never enqueued again because it is also grayed and the then clause of lines 14-17 is executed only for white vertices. Thus, the value of d[v] never changes again, and the inductive hypothesis is maintained.
|
To prove that d[v] = δ(s, v), we must first show more precisely how the queue Q operates during the course of BFS. The next lemma shows that at all times, there are at most two distinct d values in the queue.
|
Suppose that during the execution of BFS on a graph G = (V, E), the queue Q contains the vertices 〈v1, v2,..., vr〉, where v1 is the head of Q and vr is the tail. Then, d[vr] ≤ d[v1] + 1 and d[vi ] ≤ d[vi+1] for i = 1, 2,..., r - 1.
Proof The proof is by induction on the number of queue operations. Initially, when the queue contains only s, the lemma certainly holds.
For the inductive step, we must prove that the lemma holds after both dequeuing and enqueuing a vertex. If the head v1 of the queue is dequeued, v2 becomes the new head. (If the queue becomes empty, then the lemma holds vacuously.) By the inductive hypothesis, d[v1] ≤ d[v2]. But then we have d[vr] ≤ d[v1] + 1 ≤ d[v2] + 1, and the remaining inequalities are unaffected. Thus, the lemma follows with v2 as the head.
Enqueuing a vertex requires closer examination of the code. When we enqueue a vertex v in line 17 of BFS, it becomes vr+1. At that time, we have already removed vertex u, whose adjacency list is currently being scanned, from the queue Q, and by the inductive hypothesis, the new head v1 has d[v1] ≥ d[u]. Thus, d[vr+1] = d[v] = d[u] + 1 ≤ d[v1] + 1. From the inductive hypothesis, we also have d[vr] ≤ d[u] + 1, and so d[vr] ≤ d[u] + 1 = d[v] = d[vr+1], and the remaining inequalities are unaffected. Thus, the lemma follows when v is enqueued.
|
The following corollary shows that the d values at the time that vertices are enqueued are monotonically increasing over time.
|
Suppose that vertices vi and vj are enqueued during the execution of BFS, and that vi is enqueued before vj. Then d[vi] ≤ d[vj] at the time that vj is enqueued.
Proof Immediate from Lemma 22.3 and the property that each vertex receives a finite d value at most once during the course of BFS.
|
We can now prove that breadth-first search correctly finds shortest-path distances.
|
Let G = (V, E) be a directed or undirected graph, and suppose that BFS is run on G from a given source vertex s ∈ V . Then, during its execution, BFS discovers every vertex v ∈ V that is reachable from the source s, and upon termination, d[v] = δ(s, v) for all v ∈ V . Moreover, for any vertex v ≠ s that is reachable from s, one of the shortest paths from s to v is a shortest path from s to π[v] followed by the edge (π[v], v).
Proof Assume, for the purpose of contradiction, that some vertex receives a d value not equal to its shortest path distance. Let v be the vertex with minimum δ(s, v) that receives such an incorrect d value; clearly v ≠ s. By Lemma 22.2, d[v] ≥ δ(s, v), and thus we have that d[v] > δ(s, v). Vertex v must be reachable from s, for if it is not, then δ(s, v) = ∞ ≥ d[v]. Let u be the vertex immediately preceding v on a shortest path from s to v, so that δ(s, v) = δ(s, u) + 1. Because δ(s, u) < δ(s, v), and because of how we chose v, we have d[u] = δ(s, u). Putting these properties together, we have
Now consider the time when BFS chooses to dequeue vertex u from Q in line 11. At this time, vertex v is either white, gray, or black. We shall show that in each of these cases, we derive a contradiction to inequality (22.1). If v is white, then line 15 sets d[v] = d[u] + 1, contradicting inequality (22.1). If v is black, then it was already removed from the queue and, by Corollary 22.4, we have d[v] ≤ d[u], again contradicting inequality (22.1). If v is gray, then it was painted gray upon dequeuing some vertex w, which was removed from Q earlier than u and for which d[v] = d[w] + 1. By Corollary 22.4, however, d[w] ≤ d[u], and so we have d[v] ≤ d[u] + 1, once again contradicting inequality (22.1).
Thus we conclude that d[v] = δ(s, v) for all v ∈ V . All vertices reachable from s must be discovered, for if they were not, they would have infinite d values. To conclude the proof of the theorem, observe that if π[v] = u, then d[v] = d[u] + 1. Thus, we can obtain a shortest path from s to v by taking a shortest path from s to π[v] and then traversing the edge (π[v], v).
|
The procedure BFS builds a breadth-first tree as it searches the graph, as illustrated in Figure 22.3. The tree is represented by the π field in each vertex. More formally, for a graph G = (V, E) with source s, we define the predecessor subgraph of G as Gπ = (Vπ, Eπ), where
Vπ = {v ∈ V: π[v] ≠ NIL} {∪ s}
and
Eπ = {(π[v], v) : v ∈ Vπ - {s}}.
The predecessor subgraph Gπ is a breadth-first tree if Vπ consists of the vertices reachable from s and, for all v ∈ Vπ , there is a unique simple path from s to v in Gπ that is also a shortest path from s to v in G. A breadth-first tree is in fact a tree, since it is connected and |Eπ| = |Vπ| - 1 (see Theorem B.2). The edges in Eπ are called tree edges.
After BFS has been run from a source s on a graph G, the following lemma shows that the predecessor subgraph is a breadth-first tree.
|
When applied to a directed or undirected graph G = (V, E), procedure BFS constructs π so that the predecessor subgraph Gπ = (Vπ, Eπ) is a breadth-first tree.
Proof Line 16 of BFS sets π[v] = u if and only if (u v) ∈ E and δ(s, v) < ∞- that is, if v is reachable from s-and thus Vπ consists of the vertices in V reachable from s. Since Gπ forms a tree, by Theorem B.2, it contains a unique path from s to each vertex in Vπ . By applying Theorem 22.5 inductively, we conclude that every such path is a shortest path.
|
The following procedure prints out the vertices on a shortest path from s to v, assuming that BFS has already been run to compute the shortest-path tree.
PRINT-PATH(G, s, v) 1 if v = s 2 then print s 3 else if π[v] = NIL 4 then print "no path from" s "to" v "exists" 5 else PRINT-PATH(G, s, π[v]) 6 print v
This procedure runs in time linear in the number of vertices in the path printed, since each recursive call is for a path one vertex shorter.
|
Show the d and π values that result from running breadth-first search on the directed graph of Figure 22.2(a), using vertex 3 as the source.
|
|
Show the d and π values that result from running breadth-first search on the undirected graph of Figure 22.3, using vertex u as the source.
|
|
What is the running time of BFS if its input graph is represented by an adjacency matrix and the algorithm is modified to handle this form of input?
|
|
Argue that in a breadth-first search, the value d[u] assigned to a vertex u is independent of the order in which the vertices in each adjacency list are given. Using Figure 22.3 as an example, show that the breadth-first tree computed by BFS can depend on the ordering within adjacency lists.
|
|
Give an example of a directed graph G = (V, E), a source vertex s ∈ V , and a set of tree edges Eπ ⊆ E such that for each vertex v ∈ V, the unique path in the graph (V, Eπ) from s to v is a shortest path in G, yet the set of edges Eπ cannot be produced by running BFS on G, no matter how the vertices are ordered in each adjacency list.
|
|
There are two types of professional wrestlers: "good guys" and "bad guys." Between any pair of professional wrestlers, there may or may not be a rivalry. Suppose we have n professional wrestlers and we have a list of r pairs of wrestlers for which there are rivalries. Give an O(n + r)-time algorithm that determines whether it is possible to designate some of the wrestlers as good guys and the remainder as bad guys such that each rivalry is between a good guy and a bad guy. If is it possible to perform such a designation, your algorithm should produce it.
|
[1]In Chapters 24 and 25, we shall generalize our study of shortest paths to weighted graphs, in which every edge has a real-valued weight and the weight of a path is the sum of the weights of its constituent edges. The graphs considered in the present chapter are unweighted or, equivalently, all edges have unit weight.
|
|
< Day Day Up > |
|
