I'm trying to find all paths between two vertices of a directed acyclic graph using dfs. I have the following code:
[bbone=text,167]
dfs(int src, int targ) {
int i, j, w, ww = -1;
STACK s;
push(&s, src);
while (!is_empty(&s)) {
w = pop(&s);
printf("%d", w);
if (w == targ) printf("\n");
j = 0;
while (1) {
ww = prev[w][j];
if (!ww) break;
push(&s, ww);
j++;
if (j >= 4) break;
}
}
}
[/bbone]
succ[][] is the data structure for the graph such that succ[x] contains successors of x (at most 4).
[bbone=text,168]
succ[1]=[0 0 0 0]
succ[2]=[1 0 0 0]
succ[3]=[2 0 0 0]
succ[4]=[1 0 0 0]
succ[5]=[4 2 0 0]
succ[6]=[5 3 0 0]
[/bbone]
When I run dfs(6,1), it prints
6321
521
41
instead of
6321
6521
6541
There must be a simple solution but I couldn't find it. Any ideas?