Graph DFS implementation (stack usage)

[Scott Dabot]

Im trying to print out the order in which the vertexes of a graph are
pushed on to the stack then print out the order in which they are popped
off the stack. My current approach is
void dfs(struct ADJACENCY *G_adj,int v)
{
int i,u;

G_adj->mark[v]=1;
visit(v,G_adj);
while ((u=next_adj_vertex(v,G_adj))>=0) {

if (G_adj->mark==0)
{
dfs(G_adj,u);

}


}
visit(v,G_adj);
}

int visit(int v, struct ADJACENCY *G_adj)
{
printf("%c ", G_adj->vertexlabel[v]);

return v;
}

With this approach the order in which my graph should print out should
be A, B, D, E , C , F ( order in which its pushed) ... but by me adding
the visit function to the end of the dfs call , im trying to print out
the order in which its popped off ... and thus i get this:

pushed: a b d e , then popped: e d b pushed: c f popped f c popped: a

which way could i reprogram this so that it prints out pushed: a b d e c
f , popped f c e d b a ?????????

 

[Craig Barkhouse]

I don't think this NG is here to do your homework for you.

 

[Michael Mair]

Im trying to print out the order in which the vertexes of a graph are
pushed on to the stack then print out the order in which they are popped
off the stack. My current approach is
void dfs(struct ADJACENCY *G_adj,int v)
{
int i,u;

G_adj->mark[v]=1;
visit(v,G_adj);
while ((u=next_adj_vertex(v,G_adj))>=0) {

if (G_adj->mark==0)
{
dfs(G_adj,u);

}


}
visit(v,G_adj);
}

int visit(int v, struct ADJACENCY *G_adj)
{
printf("%c ", G_adj->vertexlabel[v]);

return v;
}

This is very nice and seems to be code that might work.

With this approach the order in which my graph should print out should
be A, B, D, E , C , F ( order in which its pushed) ... but by me adding
the visit function to the end of the dfs call , im trying to print out
the order in which its popped off ... and thus i get this:

pushed: a b d e , then popped: e d b pushed: c f popped f c popped: a

which way could i reprogram this so that it prints out pushed:
> a b d e c f , popped f c e d b a ?????????

Your request is offtopic around here as you are essentially asking
for an algorithm.

One way to achieve what you want is to look at what you want:
You want to print out the push order and the reverse push order.
So, the latter provides no new information. You could print
everything into a string and print the string first normal,
then in reverse.
Another, which I would prefer, is creating an index table.
Add to struct ADJACENCY an entry currindex as well as a pointer
indextable. Provide a function to reset currindex to zero and realloc()
indextable to a size s.t. it can contain all vertex indices.
Then, you start your depth first search. Every time you push a
vertex, you add its index to indextable[currindex] and increase
currindex by one.
Afterwards you can just run through your indextable in any order
you like and get the vertex labels. In addition, it separates
algorithm and output.

If you want to save memory and do not care about time complexity
or computational effort, you can instead only reset currindex to
0, increase currindex by one before pushing and writing this
increased currindex into mark.
So, afterwards you can extract the information from mark (which
unfortunately just goes the wrong direction and reversing that
will cost you -- either memory and the linear complexity of a
bucket sort, meaning you are not better off, or no memory and
higher complexity).


Cheers
Michael