Breadth-first search example Gray vertices
Bread ht -f hl irst search example r s t u Q y 1 0 2 3 r 3 2 1 2 3 Gray vertices v w x y y
Breadth-first search example Gray vertices
Bread ht -f hl irst search example r s t u Q 1 0 2 3 r ∅ 2 1 2 3 Gray vertices v w x y y
Breadth-first search algorithm BFSIG. S 1. for each vertex u EvG-is) 234 do coloru←WHTE x[←NI 5. colorIs]←GRAY 6.as]←0 7.←NIL 8.g← 9. ENQUEUE(O, S)
Bread ht -f hl h irst search algorithm BFS(G, s) 1. for each vertex u ∈ V[G] − {s} 2. do color[u] ← WHITE 3. d[u] ← ∞ 4. π[u] ← NIL 5. color[s] ← GRAY 6. d[s] ← 0 7. π[s] ← NIL 8. Q ←∅ 9. ENQUEUE(Q, s) ∅
Breadth-first search algorithm BFSIG. S 10. while O≠ 11.do← DEQUEUE(g 12. for each y∈Adll 13 do if colory =WHITE 14.O(E then colony]←GRAY、O() 15times dv]←a]+1(tmes 16. 17 ENQUEUE(O, v) 18. color[a← BLACK Running time is O(+ E)
Bread ht -f hl h irst search algorithm BFS(G, s) 10. while Q ≠ 11 d DEQUEUE(Q) ∅ 11. do u ← DEQUEUE(Q) 12. for each v ∈ Adj[u] 13. d if ocolor[v] = WHITE 14. then color[v] ← GRAY 15 d[ ] d[ ] + 1 O(V) ti O(E) 15. i d[v] ← d[u] + 1 16. π[v] ← u 17 ENQUEUE(Q ) times times 17. ENQUEUE(Q, v) 18. color[u] ← BLACK Running time is O(V + E)
Shortest paths PRINT-PATH(G, S, v 1. ify=s 2. then print s 3. else if tv=NIL then print "no path from"s to"v"exists else PRINt-PaTH(G, s, TvD) print v
Sh h ortest paths PRINT-PATH(G, s, v) 1. if v = s 2. then pri t n s 3. else if π[v] = NIL 4. then pri t " th f " int "no path from" s "t "o v " it " ex sts." 5. else PRINT-PATH(G, s, π[v] ) 6. pri t n v