Corollary 22.4 Theorem 22.5 cdu][] if u enqueued before v F(Correctness of the BFS): Let G be a -Proof. Immediate from the above lemma directed or undirected graph, and suppose that BFS is run on G from a given s in V. During the searching, it discovers all the s reachable from s, and upon Proof of theorem 22.4 证明(续) 反证法:设顶点v是 的顶点之一,则d≠svl,很显然 Edy>s,=10.【利用 V≠s,由于d≥8s,得到:dv>8[s LV是从s可到达的,否则矛盾,故有最短路径 下边说明在u出队列之时,不论v是白、 到达v,且其前一个顶点为u【一定有】,进 黑,都矛盾 而得到:8s,V=8s,u]+1 d=du+1,【白即缺省色:蓝 灰:dv≤du+1 黑:dN≤du Breadth first tree Diameter of a tree s-The procedure BFS builds a breadth-first . The diameter of a tree T=(V, E)is given tree. s is the root EMax(6(u),foru,v∈V Give an efficient solution 2①26 清华大学 宋斌恒 31 Corollary 22.4 Corollary 22.4 d[u]≤d[v] if u enqueued before v. Proof. Immediate from the above lemma. 清华大学 宋斌恒 32 Theorem 22.5 Theorem 22.5 (Correctness of the BFS): Let G be a directed or undirected graph, and suppose that BFS is run on G from a given s in V. Then, During the searching, it discovers all the vertices is reachable from s, and upon termination, d[v] = δ(s,v) One of the shortest path from s to v contains (π[v],v) if v is reachable from s. 清华大学 宋斌恒 33 Proof of Theorem 22.4 Proof of Theorem 22.4 反证法：设顶点v是不满足以上定理的距离最 短的顶点之一，则d[v] ≠ δ[s,v], 很显然， v≠s, 由于d[v] ≥δ[s,v]得到： d[v] >δ[s,v]. v 是从s可到达的，否则矛盾，故有最短路径 到达v，且其前一个顶点为u【一定有】，进 而得到： δ[s,v] ＝δ[s,u]＋1Î s v u 清华大学 宋斌恒 34 证明（续） d[v]> δ[s,v] = δ[s,u]＋1=d[u]+1.【利用假 设】 下边说明在u出队列之时，不论v是白、 灰、黑，都矛盾： 白： d[v] = d[u]+1，【白即缺省色：蓝】 灰： d[v] ≤ d[u]+1, 黑： d[v] ≤ d[u]。 而不是 d[v]> d[u]+1 ！！ 清华大学 宋斌恒 35 Breadth first tree Breadth first tree The procedure BFS builds a breadth-first tree. s is the root. 1 0 2 3 2 1 2 3 v w r t u x y s 清华大学 宋斌恒 36 Diameter of a tree Diameter of a tree The diameter of a tree T = (V, E) is given by Max(δ(u,v), for u,v ∈V) Give an efficient solution