Graph DFS implementation (stack usage)

Discussion in 'C Programming' started by Scott Dabot, Nov 10, 2004.

  1. Scott Dabot

    Scott Dabot Guest

    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 ?????????
    Scott Dabot, Nov 10, 2004
    #1
    1. Advertising

  2. I don't think this NG is here to do your homework for you.
    Craig Barkhouse, Nov 10, 2004
    #2
    1. Advertising

  3. Scott Dabot

    Michael Mair Guest

    [OT] Graph DFS implementation (stack usage)

    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==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.
    Michael Mair, Nov 10, 2004
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Sunil Thomas

    server mappath dfs share

    Sunil Thomas, Nov 9, 2003, in forum: ASP .Net
    Replies:
    0
    Views:
    494
    Sunil Thomas
    Nov 9, 2003
  2. Daniel Gardiner

    DFS Root with ASP.NET

    Daniel Gardiner, Nov 26, 2003, in forum: ASP .Net
    Replies:
    0
    Views:
    376
    Daniel Gardiner
    Nov 26, 2003
  3. Paul Moore
    Replies:
    3
    Views:
    587
    Bengt Richter
    Nov 29, 2003
  4. Emilio Mayorga
    Replies:
    6
    Views:
    313
    Martien Verbruggen
    Oct 8, 2003
  5. Replies:
    3
    Views:
    86
    Jorgen Grahn
    Apr 8, 2014
Loading...

Share This Page