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

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.

lol how did you do that with the link?

the wikipedia page doesn't explain well how to use recursion

Originally Posted by Eman

the wikipedia page doesn't explain well how to use recursion

Have you read all the article? Do you expect anyone writing a bigger explanation? I can answer a specific question.

not a bigger explanation..an easier explanation

Originally Posted by Eman

not a bigger explanation..an easier explanation

Ok, what is so hard to understand in wikipedia's explanation then?

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

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

http://www.youtube.com/watch?v=or9xlA3YYzo
DFS: treat this stack as call stack and you got recursive solution.

yeah that was the video I watched..
This is the link for what I have so far Graphs.rar
if you want to look at it and maybe you or someone else can please tell me if i have it done correctly.. I will work on the recursion now.