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 ) -> nullso output via DFS should be:

[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

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)

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

}

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?