Breadth-first search: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 3: Line 3:
<code>
<code>
  BFS(''G,s'')
  BFS(''G,s'')
   1 '''for''' each vertex ''u'' &isin; ''G.V'' - {''s''}
   1 '''for''' each vertex ''u'' &isin; ''G.V'' - {''s''}
   2      ''u.color'' = WHITE
   2      ''u.color'' = WHITE
   3      ''u.d'' = &infin;
   3      ''u.d'' = &infin;

Revision as of 16:39, 25 September 2014

Pseudocode

BFS(G,s)
 1 for each vertex uG.V - {s}
 2       u.color = WHITE
 3       u.d = ∞
 4       u.π = NIL
 5  s.color = GRAY
 6  s.d = 0
 7  s.π = NIL
 8  Q = Ø
 9  ENQUE(Q, s)
10 while Q ≠ Ø
11      u = DEQUEUE(Q)
12      for each vG.Adj[u]
13              if v.color == WHITE
14                       v.color = GRAY
15                       v.d = u.d + 1
16                       v.π = u
17                       ENQUEUE(Q, v)
18      u.color = BLACK