Review: the stack-based implementation of DFS

Stack-based implementation of the Depth First Search algorithm:

   void dfs()
   {
      int i, j;
   	  
      while ( myStack != empty )
      {
         i = myStack.pop();  // Get next node to visit

   	 visited[i] = true;  // Mark node i as "visited"
   	  
   	 /* ----------------------------------------------------------
   	    We reached node i... Something wonderful may happen at i
   	    ---------------------------------------------------------- */
   	 cout << i << endl;  // Change accordingly
   	  
   	 /* -------------------------------------------------------------
   	    How you find nodes j will depend on how you represent the graph
   	    ------------------------------------------------------------- */
   	 for ( each node j that can be reached from node i )
   	 {
   	    if ( ! visited[j] )       
   	    {
   	       myStack.push(j);  // Visit node j
   	    }  // When you loop back up, myStack.pop() will visit the node!
   	 }
      }
   } 

Breadth First Search: the queue-based implementation of graph traversal

Instead of a LIFO stack, we can also use a FIFO queue to store the "to-visit" nodes:

   void bfs()
   {
      int i, j;
   	  
      while ( myQueue != empty )
      {
         i = myQueue.remove();  // Get next node to visit

   	 visited[i] = true;  // Mark node i as "visited"
   	  
   	 /* ----------------------------------------------------------
   	    We reached node i... Something wonderful may happen at i
   	    ---------------------------------------------------------- */
   	 cout << i << endl;  // Change accordingly
   	  
   	 /* -------------------------------------------------------------
   	    How you find nodes j will depend on how you represent the graph
   	    ------------------------------------------------------------- */
   	 for ( each node j that can be reached from node i )
   	 {
   	    if ( ! visited[j] )       
   	    {
   	       myQueue.push(j);  // Visit node j
   	    }  // When you loop back up, myQueue.pop() will visit the node!
   	 }
      }
   } 

C++ solution to J5 using Stack-based DFS

#include <queue>
queue<int> xCoord, yCoord;      // Queues to store (x,y) values

void bfs()
{
   int i, j;
   int x, y;

   while ( ! xCoord.empty() )
   {
      // Visit next node
      x = xCoord.front();  xCoord.pop();
      y = yCoord.front();  yCoord.pop();

      visited[x][y] = true;     // Mark (x,y) as visited

      if ( x == M && y == N )
      {
         cout << "yes" << endl;
         exit(0);
      }

      // Go to next nodes
      for ( i = 1; i <= M; i++ )  // M can be reduced...
      {
         // DO NOT search, j can be computed as: j = grid[x][y]/i
         {  j = grid[x][y] / i;

            if ( i*j == grid[x][y] && j <= N ) // j must be value: j <= N !!!
               if ( ! visited[i][j] )
               {
                  xCoord.push(i); yCoord.push(j);   // Visit node (i,j)
               }
         }
      }
   }
}

Demo: CCC/2020/Progs/sol5-queue.cc