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 =0 u.π，起到了什么作用？ 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,沿其).π，必定找到 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 0.d,起到了什么作用？ 9 ENQUEUE(O,s) 10 while O≠g 11 =DEQUEUE(O) v.d记录了s节点到m节点路径的 12 for each v∈G.Adj[w 长度 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 4.π=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 OV+E) 17 ENQUEUE(O,v) 18 u.color BLACK
𝑶(𝑽 + 𝑬)
问题10： 为什么我们在讨论BFS 算法时特别关注算法能够正 确计算出最短路径距离？
问题10： 为什么我们在讨论BFS 算法时特别关注算法能够正 确计算出最短路径距离？
v.d是6(s,)的上界 我们要证明的结论“v.d=6(S,)” 和“v.d是6(s,v)的上界” 有什么关系？
𝑣. 𝑑 是𝛿(𝑠, 𝑣)的上界 我们要证明的结论“𝑣. 𝑑 = 𝛿(𝑠, 𝑣)” 和“𝑣. 𝑑 是𝛿(𝑠, 𝑣)的上界” 有什么关系？