Thread: DFS algorithm

  1. #1
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629

    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
    You ended that sentence with a preposition...Bastard!

  2. #2
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    Quote Originally Posted by Eman View Post
    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.

  3. #3
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    lol how did you do that with the link?

    the wikipedia page doesn't explain well how to use recursion
    You ended that sentence with a preposition...Bastard!

  4. #4
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    Quote Originally Posted by Eman View Post
    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.

  5. #5
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    not a bigger explanation..an easier explanation
    You ended that sentence with a preposition...Bastard!

  6. #6
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    Quote Originally Posted by Eman View Post
    not a bigger explanation..an easier explanation
    Ok, what is so hard to understand in wikipedia's explanation then?

  7. #7
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    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..
    Last edited by Eman; 03-18-2011 at 08:16 AM.
    You ended that sentence with a preposition...Bastard!

  8. #8
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    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.
    Last edited by kmdv; 03-18-2011 at 08:29 AM.

  9. #9
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    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.
    You ended that sentence with a preposition...Bastard!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM