CS 201 - 10/13/14

Depth First Search

   Use the stack, at the end, the stack contains
     the solution in the reverse order.


   Stack *st1;

   To reverse the order of values on a stack, a
    siomple solution is to use a second stack.

   Stack *st2;

   while ( isEmpty (st1) == false)
     {
       push (&st2, top (st1) );
       pop (&st1);
     }

For the Breadth First Search, the queue contains
   the end point of the paths, but not all the elements
   of the each path.
 
   If I maintain in the maze space (2D array that 
     contains the blocked, visited, unvisited, etc, 
     information), which location first accessed
     each locations.

In the Depth First Search, the Maze space just
   needed to know a single character of information
      *  - blocked
      .  - unvisited
      e  - end
      s  - start
      v  - visited

  The variable for the maze space could be:

       char maze[22][22];

       maze[x][y] = 'v';

For the Breadth First Search, we need more information
   stored in the Maze Space:

       We need the blocked, visited, unvisited, start,
         end as we had for the Depth First Search

       We also need this "first accessed location"
         which is two integers.


  struct MazeData
     {
       char  positionState;
       int   xFirstAccessed;
       int   yFirstAccessed;
      }

   struct MazeData mazeBFS [22][22];

       mazeBFS[x][y].positionState = 'v';


Breadth First Search  (find the shortest path)

      - get an empty queue
      - mark all unblocked locations as unvisited

      - add the start location onto the queue
      - mark the start location as visited

      while ( the queue is not Empty   AND
              the front of the queue is NOT the
              end location )
          {
            
             get & remove Front Location from Queue

             for all ( unvisited and unblocked locations
                       adjacent to this location just 
                       removed from the queue)
                {
                   add adjacent location to the queue
                   mark adjacent location as visited
                   add x,y coordinates for current location
                     to xFirstAccessed and yFirstAccessed
                     mazeSpace data for the adjacent location

                }
            }
                       
     if ( queue is empty )
        {
           no solution exists
        }
    else
        {
           front of queue is end location
        }



------------------------
    while ( isEmpty (st2) == FALSE)
      {
         print coordinate at top (st2);
         pop (&st2);
      }