BFS
Document last modified: 
BFS (G, s)
  -- post: every vertex that is reachable from s
-- is discovered and the BFS tree is created
-- in π
          
1 for each vertex u ∈ G.V - {s} do
2    u.color ← WHITE
3    u.d ← ∞
4    u.π ← NIL
  -- Initialize the source vertex and Queue
5 s.color ← GRAY
6 s.d ← 0
7 s.π ← NIL
8 Q ← |
9 Enqueue (Q, s)
  -- Perform breadth first search
10 while Q ≠ | do
11    u ← Dequeue (Q)
12    for each v ∈ G.Adj[u] do
13        if v.color = WHITE then
14           v.color ← GRAY
15           v.d ← u.d + 1
16           v.π ← u
17           Enqueue (Q, v)
18    u.color ← BLACK
  1 2 3 4 5
π NIL NIL NIL NIL NIL
d ∞ ∞ ∞ ∞ 0
color WHITE WHITE WHITE WHITE GRAY

Question

  • Execute the BFS on source vertex 5, visiting adjacent vertices at line 12 in numerical order.
  • Draw BFS tree.