Breadth-first search: Difference between revisions
Jump to navigation
Jump to search
| 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'' = ∞ | ||
4 ''u.''π = NIL | 4 ''u.''π = NIL | ||
5 ''s.color'' = GRAY | 5 ''s.color'' = GRAY | ||
6 ''s.d'' = 0 | 6 ''s.d'' = 0 | ||
7 ''s.π'' = NIL | 7 ''s.π'' = NIL | ||
8 ''Q'' = Ø | 8 ''Q'' = Ø | ||
9 ENQUE(''Q, s'') | 9 ENQUE(''Q, s'') | ||
10 '''while''' ''Q'' ≠ Ø | 10 '''while''' ''Q'' ≠ Ø | ||
11 ''u'' = DEQUEUE(''Q'') | 11 ''u'' = DEQUEUE(''Q'') | ||
12 '''for''' each ''v'' ∈ ''G.Adj''[''u''] | 12 '''for''' each ''v'' ∈ ''G.Adj''[''u''] | ||
Revision as of 16:40, 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