[prev] 18 [next]

Path Finding

BFS algorithm for path checking:

int hasPath(Graph g, Vertex src, Vertex dest)
{
   int *visited = calloc(nV(g),sizeof(int));
   Queue q = newQueue();
   QueueJoin(q,src);
   int isFound = 0;
   while (!QueueIsEmpty(q) && !isFound) {
      Vertex y, x = QueueLeave(q);
      for (y = 0; y < nV(g); y++) {
         if (!hasEdge(g,x,y)) continue;
         if (y == dest) { isFound = 1; break; }
         if (!visited[y])
            { QueueJoin(q,y); visited[y] = 1; }
      }
   }
   free(visited);
   return isFound;
}