DFS

• DFS has three versions 1) recursive 2) recursive to loop version. 3) uniformversion
  1. recursive version:
     DFS(current){ 
       visit current; 
       for all(next to current){ 
          if(unvisited(next)){ 
               DFS(next); 
           } 
        } 
     }
  2. recursive to loop
     DFS(start){ 
      S.push(start) 
       while(!S.empty()){ 
         current = top(); 
         visit current; 
         If (current has one unvisited next){ 
              stack.push(next); 
         } 
         else{ 
             stack.pop() 
         } 
     } 
     }
  3. unified version:
     DFS(start){ 
      S.push(start) 
       while(!S.empty()){ 
         current = S.pop 
         if(unvisited(current){ 
               visit current. 
               for all(next to current and unvisited) 
                  S.push(next); 
         } 
       } 
      }
• Why we need two "unvisited" words in DFS unified version.
  1. When we pop node from S, then we visit it, then we add all adjacent nodes to S, In this way, When we pop 1 from S, we add 2, 3 to S. at this time, 3 is unvisited, then when we pop 2 from S, we will add 4, 3 to S. so there are two 3 in the S.
  2. Based on, we need to first unvisit to avoid visit 3 twice
  3. When we reach 3; 1,2,4 have been visited, so when we want to add all 3 adjacent, we need second unvisited to avoid 1,2,4 to S.
       1  
    /    \  
   2----3  
   \     /  
      4

• DFS is an algorithm to search a hierarchical structure. But, pre-order traversal seems to be something similar also. So, what is the difference between the two?? DFS says:
  1. If element found at root, return success.
  2. If root has no descendants, return failure
  3. Recursive DFS on left subtree: success if element found
  4. If not, Recursive DFS on right subtree: success if element found

  Pre-order Traversal says:

  1. Visit the root
  2. Recursive pre-order on left subtree
  3. Recursive pre-order on right subtree