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..

```
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);
}
}
}

}

```

And even simpler..

```
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);
}
}
}

}

```

Comments are closed.