Velocity Reviews > Graph DFS implementation (stack usage)

# Graph DFS implementation (stack usage)

Scott Dabot
Guest
Posts: n/a

 11-10-2004
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[u]==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
Guest
Posts: n/a

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

Michael Mair
Guest
Posts: n/a

 11-10-2004
Scott Dabot wrote:

> 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[u]==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
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post George Sakkis Python 1 01-29-2007 11:09 PM Jef Driesen C++ 3 01-24-2006 01:44 PM Dr Ann Huxtable C Programming 6 12-21-2004 11:15 AM Paul Moore Python 3 11-29-2003 11:03 PM Emilio Mayorga Perl Misc 6 10-08-2003 02:14 AM

Advertisments