v.d的上限 间题8： 你能解驿是怎么归纳的吗？ Lemma 22.2 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 ver- tex v EV,the value v.d computed by BFS satisfies v.d >(s,v). Proof We use induction on the number of ENQUEUE operations.Our inductive hypothesis is that v.d≥8(s,v)for all v∈V. The basis of the induction is the situation immediately after enqueuing s in line 9 of BFS.The inductive hypothesis holds here,because s.d =0=8(s,s)and v.d=o≥8(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 u.d >(s,u).From the assignment performed by line 15 and from Lemma 22.1,we obtain v.d u.d+1 8(s,u)+1 为什么？ 8(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 v.d never changes again,and the inductive hypothesis is maintained. ■v.d 的上限 为什么？