[prev] 56 [next]

Finding a Path (cont)

DFS algorithm:

int isPath(Graph g, Vertex v, Vertex w)
{
   int *visited = calloc(g->nV,sizeof(int));
   Stack s = newStack();
   StackPush(s, v);
   while (!StackEmpty(s)) {
      Vertex y, x = StackPop(s);
      foreach (y in neighbours(x)) {
         if (y == w) return TRUE;
         if (!visited[y]) {
            StackPush(s, y);
            visited[y] = 1;
         }
      }
   }
   return FALSE;
}