Review: the recursive Depth First Search algorithm

Recursive Depth First Search:

   bool visited[N];

   void dfs(int i)
   {
      int j;

      visited[i] = true;  // Mark node i as "visited"

      /* ---------------------------------------------------------------
         We reached node i... Something wonderful may happen at i
         I print node i out - Replace with code that solves your problem
         --------------------------------------------------------------- */
      cout << i << endl;  // Debug use

      /* ---------------------------------------------------------------
         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] )       
         {
            dfs(j);  // Function calls are LIFO
         }
      }
   } 

Another way to implement the Depth First Search algorithm

Depth First Search can also be implemented using a stack (which is LIFO):

   bool visited[N];

   void dfs(int i)
   {
      int j;

      visited[i] = true;  // Mark node i as "visited"

      /* ---------------------------------------------------------------
         We reached node i... Something wonderful may happen at i
         I print node i out - Replace with code that solves your problem
         --------------------------------------------------------------- */
      cout << i << endl;  // Debug use

      /* ---------------------------------------------------------------
         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] )       
         {
            dfs(j);  // Use a stack to store to-visit nodes
         }
      }
   } 

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!
   	 }
      }
   } 

Solution to J5 using Stack-based DFS

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

   while ( ! xCoord.empty() )
   {
      // Visit next node
      x = xCoord.top();  xCoord.pop();
      y = yCoord.top();  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-stack.cc