BFS

• There are two version of BFS:
  1. Form DFS unify version, We can change S(stack) to Q(queue) and get unified version. That is why we call it unified version
     BFS(start){ 
      Q.push(start) 
       while(!Q.empty()){ 
         current = Q.pop 
         if(unvisited(current){ 
               visit current. 
               for all(next to current and unvisited) 
                  Q.push(next); 
         } 
       } 
      }
  2. Common version: Unified version will have multi-copy vertex in the queue. We can improve it as below: 1) when you add it to queue, visit it. In this way, avoid add multi-copy vertex in queue 2) Because All the vertex in queue is visited, when you pop it, you don’t need to judge if it’s visisted.
     DFS(start){ 
      D.push(start) 
       while(!D.empty()){ 
         current = D.pop  //2) no if here 
         for all(next to current and unvisited){ 
              visit current.  //1) push and visit at the same time. 
              D.push(next); 
          } 
       } 
      }
  3. conclusion:
     1. Conclusion, just remember unified version. 1) pop current, push neighbor, 2) check two unvisited
     2. unified version will push two nodes into stack or queue, so for BFS, you can visit and push at the same time, in this way, you don’t need to check current if it is unvisited.
     3. For DFS, you can’t use this way, because you can only visit only one neighbor, or it will become BFS. so each time, you just push one node into stack. It leads to two other versions. recursive version, and loop version.
• Path is saved in the stack. when you quit while loop. just pop up each position from stack, then you get a path. But for BFS, you need extra information to save parent information.