BFS(G,s) .d是δ(s,v)的上界 1 for each vertex u G.V-{s} 2 u.color WHITE Lemma 22.2 Let G =(V,E)be a directed or undirected graph,and suppose that BFS is run 3 u.d =oo on G from a given source vertex s e V.Then upon termination,for each ver- 4 2u.π=NI tex vE V,the value v.d computed by BFS satisfies v.d >8(s.v). 5 s.color GRAY Proof We use induction on the number of ENQUEUE operations.Our inductive 6 s.d=0 hypothesis is that v.d≥8(s,v)for all v∈V. 7 S.π=NIL The basis of the induction is the situation immediately after enqueuing s in line 9 8 of BFS.The inductive hypothesis holds here,because s.d =0 =8(s,s)and Q=0 v.d=oo≥8s,v)for allv∈V-{s. 9 ENQUEUE(O,s) For the inductive step,consider a white vertex v that is discovered during the 10 while O≠0 search from a vertex u.The inductive hypothesis implies that u.d>(s.u).From the assignment performed by line 15 and from Lemma 22.1,we obtain 11 =DEQUEUE(O) 12 =u.d+1 for each v∈G.Adju v.d 为什么？ 13 if v.color =WHITE ≥ 8s,0)+ 8(s,v) 14 v.color GRAY 15 Vertex v is then enqueued,and it is never enqueued again because it is also grayed v.d u.d+1 and the then clause of lines 14-17 is executed only for white vertices.Thus,the 16 V.π=2l value of v.d never changes again.and the inductive hypothesis is maintained. 17 ENQUEUE(O,v) 18 u.color BLACKv.d 是δ(s,v)的上界 为什么？