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