Hello, I need clarification on the DFS algorithm..
I was watching a video on how to how to traverse a graph using this algorithm.
The guy was picking the smallest unvisited vertex connected to the current vertex.
The the new smallest vertex becomes the current vertex..
i followed his method but that meant finding the smallest node in the sub graph.
But then I was reading another tutorial, and the guy didn't pick the smallest unvisited node. So i figured computing the lowest unvisited node might be inefficient. So I wrote this..but I can't find any C++ code I can understand to see if how I did it is correct.
If what I did above is reasonably correct..how can I implement dfs using recursion..I don't really understand how to work on that.Code:bool done = false ;
int unvisited =1;
stack.push(unvisited) ;
Node *t = arr[unvisited] ;
visited[unvisited] = 1 ;
while(!done)
{
if(visited[t->vertex]==0)
{
visited[t->vertex] = 1;
unvisited = t->vertex ;
stack.push(unvisited) ;
t = arr[unvisited] ;
}
else
{
while(t->next!=NULL&&visited[t->vertex]==1)
{
t= t->next ;//Find the next unvisited node
}
if(t->next==NULL)
{
//if in this condition..it means that all the vertex connected to
//the current vertex by an edge are visited
int d = stack.pop(); //pop the current vertex from the stack
int f = stack.top(); //get the top of the stack
//if it returns -1.it means I can't pop any more stuff.
// means loop has finished?
if(f!=-1)
t = arr[f] ;
else
done = true ;
}
}
}
Thanks