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