[prev] 54 [next]

Finding a Path (cont)

BFS algorithm:

int isPath(Graph g, Vertex v, Vertex w)
{
   int *visited = calloc(g->nV,sizeof(int));
   Queue q = newQueue();
   QueueJoin(q, v);
   while (!QueueEmpty(q)) {
      Vertex y, x = QueueLeave(q);
      foreach (y in neighbours(x)) {
         if (y == w) return TRUE;
         if (!visited[y]) {
            QueueJoin(q, y);
            visited[y] = 1;
         }
      }
   }
   return FALSE;
}