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); }