BFS

powered by FreeFind

Modified: 
BFS (G, s)
         -- Initialize arrays
1 for each vertex u Î V[G] - {s} do
2    color[u] ¬ WHITE
3    d[u] ¬ ¥
4    p[u] ¬ NIL
  -- Initialize the source vertex and Queue
5 color[s] ¬ GRAY
6 d[s] ¬ 0
7 p[s] ¬ NIL
8 Q ¬ Æ
9 Enqueue (Q, s)
  -- Perform breadth first search
10 while Q ¹ Æ do
11    u ¬ Dequeue (Q)
12    for each v Î Adj[u] do
13        if color[v] = WHITE then
14           color[v] ¬ GRAY
15           d[v] ¬ d[u] + 1
16           p[v] ¬ u
17           Enqueue (Q, v)
18    color[u] ¬ BLACK
  1 2 3 4 5
p 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.