Breadth-first search: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Pseudocode == <code> BFS(''G, s'') 1 '''for''' each vertex ''u'' ∈ ''G.V'' - {s} 2 ''u.color'' = WHITE 3 ''u.d'' = ∞ 4 ''u.''π =...") |
|||
| Line 3: | Line 3: | ||
<code> | <code> | ||
BFS(''G, s'') | BFS(''G, s'') | ||
1 '''for''' each vertex ''u'' ∈ ''G.V'' - {s} | 1 '''for''' each vertex ''u'' ∈ ''G.V'' - {''s''} | ||
2 ''u.color'' = WHITE | 2 ''u.color'' = WHITE | ||
3 ''u.d'' = ∞ | 3 ''u.d'' = ∞ | ||
Revision as of 16:29, 25 September 2014
Pseudocode
BFS(G, s)
1 for each vertex u ∈ G.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 v ∈ G.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