int findPath(Graph g, Vertex src, Vertex dest)
{
Vertex *path = malloc(nV(g) * sizeof(Vertex));
int *visited = calloc(nV(g),sizeof(int));
Queue q = newQueue();
QueueJoin(q,src);
int isFound = 0;
while (!emptyQ(q) && !isFound) {
Vertex y, x = QueueLeave(q);
for (y = 0; y < nV(g); y++) {
if (!hasEdge(g,x,y)) continue;
if (!visited[y])
{ path[y] = x; QueueJoin(q,y); visited[y] = 1; }
if (y == dest) { isFound = 1; break; }
}
}
if (isFound) {
Vertex v;
for (v = dest; v != src; v = path[v])
printf("%d-", v);
printf("%d\n", src);
}
free(visited); free(path);
return isFound;
}
|