Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 102
Текст из файла (страница 102)
If v is white, then it hasnot yet been discovered, and the algorithm discovers it by executing lines 14-17. It is firstgrayed, and its distance d[v] is set to d[u]+1. Then, u is recorded as its parent. Finally, it isplaced at the tail of the queue Q. When all the vertices on u's adjacency list have beenexamined, u is blackened in lines 11-18. The loop invariant is maintained because whenever avertex is painted gray (in line 14) it is also enqueued (in line 17), and whenever a vertex isdequeued (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 agiven vertex are visited in line 12: the breadth-first tree may vary, but the distances dcomputed by the algorithm will not.
(See Exercise 22.2-4.)AnalysisBefore proving the various properties of breadth-first search, we take on the somewhat easierjob of analyzing its running time on an input graph G = (V, E). We use aggregate analysis, aswe saw in Section 17.1. After initialization, no vertex is ever whitened, and thus the test inline 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 queueoperations is O(V). Because the adjacency list of each vertex is scanned only when the vertexis dequeued, each adjacency list is scanned at most once.
Since the sum of the lengths of allthe adjacency lists is Θ(E), the total time spent in scanning adjacency lists is O(E). Theoverhead 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.Shortest pathsAt the beginning of this section, we claimed that breadth-first search finds the distance to eachreachable vertex in a graph G = (V, E) from a given source vertex s V. Define the shortestpath distance δ(s, v) from s to v as the minimum number of edges in any path from vertex s tovertex v; if there is no path from s to v, then δ(s, v) = ∞. A path of length δ(s, v) from s to v issaid to be a shortest path[1] from s to v.
Before showing that breadth-first search actuallycomputes shortest-path distances, we investigate an important property of shortest-pathdistances.Lemma 22.1Let G = (V, E) be a directed or undirected graph, and let sfor any edge (u, v) E,V be an arbitrary vertex. Then,δ(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 belonger than the shortest path from s to u followed by the edge (u, v), and thus the inequalityholds. 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 vshow that d[v] bounds δ(s, v) from above.V. We firstLemma 22.2Let G = (V, E) be a directed or undirected graph, and suppose that BFS is run on G from agiven 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 isthat 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 vV - {s}.For the inductive step, consider a white vertex v that is discovered during the search from avertex u. The inductive hypothesis implies that d[u] ≥ δ(s, u).
From the assignment performedby line 15 and from Lemma 22.1, we obtaind[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 thethen clause of lines 14-17 is executed only for white vertices.
Thus, the value of d[v] neverchanges again, and the inductive hypothesis is maintained.To prove that d[v] = δ(s, v), we must first show more precisely how the queue Q operatesduring the course of BFS. The next lemma shows that at all times, there are at most twodistinct d values in the queue.Lemma 22.3Suppose that during the execution of BFS on a graph G = (V, E), the queue Q contains thevertices v1, v2,..., vr , where v1 is the head of Q and vr is the tail. Then, d[vr] ≤ d[v1] + 1 andd[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 queuecontains only s, the lemma certainly holds.For the inductive step, we must prove that the lemma holds after both dequeuing andenqueuing a vertex.
If the head v1 of the queue is dequeued, v2 becomes the new head. (If thequeue 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 areunaffected. Thus, the lemma follows with v2 as the head.Enqueuing a vertex requires closer examination of the code. When we enqueue a vertex v inline 17 of BFS, it becomes vr+1. At that time, we have already removed vertex u, whoseadjacency 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 theinductive 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 aremonotonically increasing over time.Corollary 22.4Suppose that vertices vi and vj are enqueued during the execution of BFS, and that vi isenqueued 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 valueat most once during the course of BFS.We can now prove that breadth-first search correctly finds shortest-path distances.Theorem 22.5: (Correctness of breadth-first search)Let G = (V, E) be a directed or undirected graph, and suppose that BFS is run on G from agiven source vertex s V . Then, during its execution, BFS discovers every vertex v V thatis 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 shortestpath 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 equalto its shortest path distance. Let v be the vertex with minimum δ(s, v) that receives such anincorrect 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 thevertex 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 theseproperties together, we have(22.1)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 acontradiction to inequality (22.1). If v is white, then line 15 sets d[v] = d[u] + 1, contradictinginequality (22.1). If v is black, then it was already removed from the queue and, by Corollary22.4, we have d[v] ≤ d[u], again contradicting inequality (22.1). If v is gray, then it waspainted gray upon dequeuing some vertex w, which was removed from Q earlier than u andfor 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 bediscovered, for if they were not, they would have infinite d values.
To conclude the proof ofthe theorem, observe that if π[v] = u, then d[v] = d[u] + 1. Thus, we can obtain a shortest pathfrom s to v by taking a shortest path from s to π[v] and then traversing the edge (π[v], v).Breadth-first treesThe procedure BFS builds a breadth-first tree as it searches the graph, as illustrated in Figure22.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π), whereVπ = {vV: π[v] ≠ NIL} {s}andEπ = {(π[v], v) : vVπ - {s}}.The predecessor subgraph Gπ is a breadth-first tree if Vπ consists of the vertices reachablefrom s and, for all v Vπ , there is a unique simple path from s to v in Gπ that is also a shortestpath 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 thepredecessor subgraph is a breadth-first tree.Lemma 22.6When applied to a directed or undirected graph G = (V, E), procedure BFS constructs π so thatthe 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 isreachable from s-and thus Vπ consists of the vertices in V reachable from s.
Since Gπ forms atree, by Theorem B.2, it contains a unique path from s to each vertex in Vπ . By applyingTheorem 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 thatBFS has already been run to compute the shortest-path tree.PRINT-PATH(G, s, v)1 if v = s2then print s3else if π[v] = NIL4then print "no path from" s "to" v "exists"5else PRINT-PATH(G, s, π[v])6print vThis procedure runs in time linear in the number of vertices in the path printed, since eachrecursive call is for a path one vertex shorter.Exercises 22.2-1Show the d and π values that result from running breadth-first search on the directed graph ofFigure 22.2(a), using vertex 3 as the source.Exercises 22.2-2Show the d and π values that result from running breadth-first search on the undirected graphof Figure 22.3, using vertex u as the source.Exercises 22.2-3What is the running time of BFS if its input graph is represented by an adjacency matrix andthe algorithm is modified to handle this form of input?Exercises 22.2-4Argue that in a breadth-first search, the value d[u] assigned to a vertex u is independent of theorder in which the vertices in each adjacency list are given.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
