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
Question
  • Execute the BFS on source vertex 5, visiting adjacent vertices at line 12 in numerical order.
      1 2 3 4 5
    π NIL NIL NIL NIL NIL
    d ∞ ∞ ∞ ∞ 0
    color WHITE WHITE WHITE WHITE GRAY

    Q=<5>
      1 2 3 4 5
    π 5 5 NIL 5 NIL
    d 1 1 ∞ 1 0
    color GRAY GRAY WHITE GRAY BLACK

    Q=<1,2,4>
      1 2 3 4 5
    π 5 5 NIL 5 NIL
    d 1 1 ∞ 1 0
    color BLACK GRAY WHITE GRAY BLACK

    Q=<2,4>
      1 2 3 4 5
    π 5 5 2 5 NIL
    d 1 1 2 1 0
    color BLACK BLACK GRAY GRAY BLACK

    Q=<4,3>
      1 2 3 4 5
    π 5 5 2 5 NIL
    d 1 1 2 1 0
    color BLACK BLACK GRAY BLACK BLACK

    Q=<3>
      1 2 3 4 5
    π 5 5 2 5 NIL
    d 1 1 2 1 0
    color BLACK BLACK BLACK BLACK BLACK

    Q=|
  • Draw BFS tree.

        5
      / | \
     1 2 4
        |
        3