Thread: 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?

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);