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 b 0 11 2 u.color WHITE 3 u.d=o∞ 4 L.π=NIL 2 c r t x (d) e t x v 5 S.color GRAY 122 2 222 6 s.d=0 7 S.π=NIL 8 2=0 e x v u y ny 9 ENQUEUE(O,s) 223 233 10 while O≠0 11 u= DEQUEUE(O) 12 foreach v∈G.Adiu g u y (h) 13 if v.color ==WHITE 33 14 v.color GRAY 15 v.d u.d+l 16 V.π=W 17 ENQUEUE(O,v) 18 u.color BLACK
BFS(G,s) 1 for each vertex u G.V-{s} 2 u.color WHITE 问题98 3 u.d=o∞ 4 4.π=NIL 5 S.color GRAY 为什么谎广度优 6 s.d=0 7 S.π=NL 先搜家的代价是 8 Q=0 9 ENQUEUE(O,s) 线性的？其问题 10 while O≠0 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.π=4 17 ENQUEUE(O,v) 18 u.color BLACK
问题10： 为什么我们在讨论BFS 算法时特别关注算法能够正 确计算出最短路径距离？
问题10： 为什么我们在讨论BFS 算法时特别关注算法能够正 确计算出最短路径距离？