# DFS algorithm

• 03-18-2011
Eman
DFS algorithm
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.
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 ;                                 }                         }                                         }```
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.

Thanks
• 03-18-2011
kmdv
Quote:

Originally Posted by Eman
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.

Thanks

Let me google that for you

The simplest and most obvious way to implement DFS is recursion and this algorithm you are entirely given there. It picks any, not yet visited vertex.
• 03-18-2011
Eman
lol how did you do that with the link?

• 03-18-2011
kmdv
Quote:

Originally Posted by Eman

Have you read all the article? Do you expect anyone writing a bigger explanation? I can answer a specific question.
• 03-18-2011
Eman
not a bigger explanation..an easier explanation
• 03-18-2011
kmdv
Quote:

Originally Posted by Eman
not a bigger explanation..an easier explanation

Ok, what is so hard to understand in wikipedia's explanation then?
• 03-18-2011
Eman
ok..the thing is I find so many different explanations of how dfs iterative search works I am not sure I am doing it the right way or which is the right way.
Code:

```Graph :: DFS_iter( Vertex s) Begin   Stack s   id = 0   for v = 1 to V   visited[v] = 0   s.push(s)   while (not s.isEmpty())   v = s.pop()   if (not visited[v])   visited[v] = ++id   for each vertex u  adj(v)   if (not visited[u])   s.push(u)//shouldn't there be a break here? or something   end while End```
that is the algorithm I was given by my lecturer..but it looks to me as if it should be for BFS.
using this algorithm he is going through all the adjacent nodes of the current vertex and pushing them to the stack if unvisited...isn't that BFS? apart from using the queue...

if i start from node A.i find an unvisited node B then push it to the stack, I leave node A and find unvisited node B until I reach a dead end then backtrack.

And for recursion..we got this algorithm
Code:

```  Graph :: DFS( Vertex s)   Begin   id = 0   for v = 1 to V   visited[v] = 0   dfsVisit(s)   End   Graph :: dfsVisit( Vertex v)   Begin   visited[v] = ++id   for each vertex u  adj(v)   if not visited[u]   dfsVisit(u)   End```
again..it sounds like bfs to me..
i go through all the adj nodes of vertex A..if they're unvisited recursively call the function and mark them as visited. what happens if there are no nodes to visit? but other branches are unvisited? my brain hurts..
• 03-18-2011
kmdv
Quote:

And for recursion..we got this algorithm
Code:

```  Graph :: DFS( Vertex s)   Begin   id = 0   for v = 1 to V   visited[v] = 0   dfsVisit(s)   End   Graph :: dfsVisit( Vertex v)   Begin   visited[v] = ++id   for each vertex u  adj(v)   if not visited[u]   dfsVisit(u)   End```
again..it sounds like bfs to me..
i go through all the adj nodes of vertex A..if they're unvisited recursively call the function and mark them as visited. what happens if there are no nodes to visit? but other branches are unvisited? my brain hurts..
No, BFS pushes vertices back and pops them front (queue). In the iterative method of DFS they are pushed back and popped back (stack).

In DFS, when there are no vertices to visit, function will return. This is equivalent to "pop from the stack" in the iterative method.

In other words: the recursive version of DFS uses call stack:
call DFS function = push vertex
return from DFS function = pop vertex