Author: techfox9
Breadth first search traversal algorithm..
Wednesday, December 2nd, 2009 @ 12:49 am
http://en.allexperts.com/q/Computer-Science-3197/Bread-First-Search-Algorithm.htm
BFS(G, s) for each vertex u in V - { s } do u.color = white u.dist = infinity // ''dist'' is distance from s u.pred = nil // ''pred'' is predecessor s.color = gray s.dist = 0 s.pred = nil Q = { s } // ''Q'' is a FIFO queue while Q not empty do u = Q.head // get element on top of queue for each v in neighbors(u) do // visit every node u has an edge to if v.color == white then v.color = gray v.dist = u.dist + 1 v.pred = u Q.enqueue(v) // add v to back of queue Q.dequeue // pop u off top of queue u.color = black
And a bit more Java-ish..
[java]
BFS(root) {
cn = root;
s.push(cn.getValue()); // Save node value on stack
cn.setValue(-1); // mark node visited
q.enqueue(cn);
while(! q.isEmpty() ) {
cn = q.dequeue();
foreach v in cn.getChildren() {
if (v.getValue() != -1) {
// This node not visited yet
s.push(v.getValue()); // save node value on stack
v.setValue(-1); // mark node visited
q.enqueue(v);
}
}
}
}
[/java]
And even simpler..
[java]
BFS(root) {
cn = root;
cn.visit(); // mark node visited
q.enqueue(cn);
while(! q.isEmpty() ) {
cn = q.dequeue();
foreach v in cn.getChildren() {
if ( ! v.visited() ) {
// This node not visited yet
v.visit(); // mark node visited
q.enqueue(v);
}
}
}
}
[/java]