[prev] 13 [next]

Breadth-first Search

BFS algorithm (records visiting order):

int *visited; // array [0..V-1] of visiting order

void bfs(Graph g, Vertex v)
{
   int i, order = 1;
   visited = calloc(nV(g),sizeof(int));
   Queue q = newQueue();
   QueueJoin(q,v);
   while (!QueueIsEmpty(q)) {
      Vertex y, x = QueueLeave(q);
      if (visited[x]) continue;
      visited[x] = order++;
      for (y = 0; y < nV(g); y++) {
         if (!hasEdge(g,x,y)) continue;
         if (!visited[y]) QueueJoin(q,y);
      }
   }
}