graph dfs troubles

This is a discussion on graph dfs troubles within the C++ Programming forums, part of the General Programming Boards category; I'm stuck on how the Depth first search outputs vertex 7, 9 for the given example using adjaceny lists: The ...

  1. #1
    Registered User
    Join Date
    Jul 2012
    Posts
    87

    graph dfs troubles

    I'm stuck on how the Depth first search outputs vertex 7, 9 for the given example using adjaceny lists:
    The square brackets b/c it's an array of linked lists (so all adjacent nodes withing a given index).

    [0] -> ( 1 ) -> ( 5 ) -> null
    [1] -> ( 2 ) -> ( 3 ) -> ( 5 ) -> null
    [2] -> ( 4 ) -> null
    [3] -> null
    [4] -> ( 3 ) -> null
    [5] -> ( 6 ) -> null
    [6] -> ( 8 ) -> null
    [7] -> ( 3 ) -> ( 8 ) -> null
    [8] -> ( 10 ) -> null
    [9] -> ( 4 ) -> ( 7 ) -> ( 10 ) -> null
    [10] -> null

    so output via DFS should be:
    0,1,2,4,3,5,6,8,10,7,9

    but when I trace w/ a stack, once I reach 10 which has no adjacent vertices to it, I return and keep returning to each caller, but no where do I ever store the vertices 7, 9 during the recursive calls,

    this is the code I'm using from textbook by D.S.Malik (Data Structures using C++ 2nd ed)
    Code:
    void graphType::dft(int v, bool visited[])
    {
      visited[v] = true;
      cout << " " << v << " ";//visit the vertex
      linkedListIterator<int> graphIt;
    
      //for each vertext adjacent to v
      for ( graphIt = graph[v].begin(); graphIt != graph[v].end(); ++graphIt )
      {
        int w = *graphIt;
        
        if ( !visited[w] )
           dft(w, visited);
      }
    }
    
    int main()
    {
      set_to_false(&visited[0]);//initially all vertices are unvisisted (so bool false)
      dft(0, visited);//perform DFS starting @ vertex 0
      return 0;
    }
    I never "push" the stack frame for vertices 7, 9. This is the call stack for each stack frame I have. Appreciate if someone point out what I'm doing wrong. I'll use an alphabet to distinguish each recursive call.

    main calls: dft( v = 0 )
    output so far: 0
    graph[v = 0].begin is 1, not visited yet so call: dft(v = 1 )

    dft( v = 1)//A
    output so far: 0 1
    graph[v = 1].begin is 2, not visited yet so call: dft(v = 2 )

    dft( v = 2 ) //B
    output so far: 0 1 2
    graph[ v = 2].begin is 4, not visited yet so call: dft( v = 4 )

    dft(v = 4)//C
    output so far: 0 1 2 4
    graph[v = 4].begin is 3, not visited yet so call: dft( v = 3)

    dft(v = 3)//D
    output so far: 0 1 2 4 3
    graph[v = 3].begin is null (dead end, so backtrack)

    so current top stack frame is caller C.
    but no items not visited after node 3 (array index 4), so return to caller B,
    but no items not visited after node 2 (array index 2 ), so return to caller A

    so in for loop of stack frame A, we visit node 5, not visited yet so call: dft(v = 5)

    dft( v = 5 )//E (i'm using new symbol to not get mixed up)
    output so far: 0 1 2 4 3 5
    graph[v = 5 ].begin is 6, not visited yet so call: dft(v = 6)

    dft(v = 6)//F
    output so far:0 1 2 4 3 5 6
    graph[v = 6].begin is 8, not visited yet so call(traverse its adjacent node): dft( v = 8)

    dft(v = 8 )//G
    output so far:0 1 2 4 3 5 6 8
    graph[v = 8].begin is 10, not visited yet so all: dft(v = 10)

    dft(v = 10)//H
    output so far: 0 1 2 4 3 5 6 8 10
    graph[v = 10].begin is null, so backtrack to caller G

    but nothing else to traverse in current stack frame G, so backtrack to caller F, so same thing, back up to E etc..

    So I'm tracing wrong of course but I can't figure out what it is since each time I return, where do I have the chance to visit vertext 7, 9?
    Last edited by monkey_c_monkey; 09-27-2012 at 07:01 PM.

  2. #2
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    It seems you need to rap your dft call in main in a for loop through the visited array:
    Code:
    for (int v = 0; v < visited.size(); v++)
        if (!visited[v])
            dft(v, visited);
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  3. #3
    Registered User
    Join Date
    Jul 2012
    Posts
    87
    So you mean in main it be:
    for each index
    for each adjacent vertex to current vertex @ graph[i].begin

    also, begin refers to the head pointer, right, and NOT the first node (since it's an array of ptrs where each index stores a ptr to a LL)?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C graph
    By nasser in forum C Programming
    Replies: 6
    Last Post: 03-26-2011, 06:21 AM
  2. Bar graph troubles
    By knightmare in forum C Programming
    Replies: 11
    Last Post: 10-25-2010, 11:41 PM
  3. need help with sin(x) and bar graph
    By SuPaNooB in forum C Programming
    Replies: 6
    Last Post: 10-07-2007, 02:01 AM
  4. Graph
    By fkheng in forum C Programming
    Replies: 8
    Last Post: 07-05-2003, 11:57 PM
  5. Bar graph
    By robjules in forum C++ Programming
    Replies: 3
    Last Post: 11-28-2001, 10:55 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21