BFS(G.s) 1 for each vertex u G.V-{s} 2 u.color WHITE 3 u.d =oo 4 u.π=NIL S S.color GRAY 6 s.d=0 问题7： 7 S.π=NIL 8 2=0 u.T,起到了什么作用？ 9 ENQUEUE(O,s) 10 while O≠g 11 =DEQUEUE(O) 除了s节点的前驱是nil外，每个 12 for each v∈G.Adj[ 节点，有且仅有一个“前驱节点” 13 if v.color =WHITE 14 v.color GRAY 15 v.d u.d+1 任意节点V,沿其V.T,必定找到 16 v.π=u 一条从s到v的路径Path 17 ENQUEUE(O,V) 18 u.color BLACK
BFS(G.s) 1 for each vertex u G.V-{s 2 u.color WHITE 3 ud=xo 4 u.π=NIL 5 s.color GRAY 6s.d=0 问题8： 7S.π=NIL 8 Q=0 V.d,起到了什么作用？ 9 ENQUEUE(O,s) 10 while O≠0 11 =DEQUEUE(O) V.d记录了s节点到v节点路径的 12 for each v∈G.Adj[u 长度 13 if v.color =WHITE 14 v.color GRAY V.d是原图中s节点到v节点的最 15 v.d=u.d+l 16 v.π=u 短路径吗？ 17 ENQUEUE(O,V) 18 u.color BLACK
BFS(G,s) 1 for each vertex u G.V-{s} 2 u.color WHITE 问题9 3 u.d=o∞ 4 u.π=NIL J S.color GRAY 为什么说广度优先 6 s.d=0 7s.π=NIL 搜家的代价是幾性 8 Q=0 9 ENQUEUE(O,s) 的？其问题规模是 10 while O≠g 11 DEQUEUE(O) 用什么参数表示的？ 12 for each v∈G.Adju 13 if v.color =WHITE 14 v.color GRAY 15 v.d u.d+1 16 v.π=W 17 ENQUEUE(O,v) 18 u.color BLACK
问题10： 为什么我们在讨论BFS 算法时特别关注算法能够正 确计算出最短路径距离？
问题10： 为什么我们在讨论BFS 算法时特别关注算法能够正 确计算出最短路径距离？
.d是(s,)的上界 我们要证明的结论“v.d=δ(s,v)” 和“.d是δ(s,v)的上界” 有什么关系？
v.d 是δ(s,v)的上界 我们要证明的结论“v.d =δ(s,v)” 和“v.d 是δ(s,v)的上界” 有什么关系？