Now that we have a database we can begin to implement the Breadth-First Search algorithm in BFS-1:
The database will also be used to implement the Depth-First Search Algorithm as well as the A* algorithm.
void AddPath(PathRecord, City, Neighbor);
A useful subroutine to make the Breadth-First Search Routine code a little more compact is returning the City with
the same name as the neighbors. This city will be designated a child city of the current city we are evaluating. The code for extracting the City
with the same name as one of the neighbors is as follows:
bool GetChildCity(Neighbor Parent, City* ChildCity)
bool BreadthFirstSearch(string StartName, string EndName): The function is of type boolean, returning true for success, a path
found, or false for failure to find a path.
City StartCity; This is the City structure corresponding to the StartName string sent as a parameter.
City CurrentCity: This City structure is used to extract data from the Frontier queue.
City ChildCity: This City structure contains the City with the same name as the unexplored Neighbor under analysis.
City ExploredCity: This City structure is used to extract City structures from the Explored queue
City FrontierCity: This City structure is used to extract data from the Frontier queue to determine if the Child City
matches a city already in the queue.
Neighbor CurrentNeighbor: This Neighbor structure is used to parse the Neighbors structure of the Current City
vector<City>::iterator CityNumber: Iterator to parse through Cities vector.
vector<Neighbor>::iterator NeighborNumber: Iterator to parse through a Neighbor vector.
vector<PathRecord>::iterator PathNumber: Iterator to parse through the PathRecord vector.
deque<City> Frontier: Queue to coordinate exploring of unexplored Cities.
deque<City> Explored: Queue to keep record of explored cities.
deque<City>::iterator FrontierCityNumber: Iterator to parse through Frontier Queue.
deque<City>::iterator ExploredCityNumber: Iterator to parse through Explored Queue.
PathRecord NewRecord(StartName): Record of paths used to create paths traversed and save data to PathsTraveled vector
PathRecord TemporaryRecord(""): Record used to extract data from PathsTraveled vector
bool StartCityFound: Flag used to indicate whether or not requested start position is in the available database.
bool GoalFound: Flag used to indicate whether or not search was successful (function return value).
bool AlreadyExplored: Flag used to indicate whether the current Neighbor City under analysis has been explored.
bool AlreadyInFrontier: Flag used to indicate whether the current Neighbor City under analysis has been placed in the
bool PathFound: Flag used to indicate if the path to the current Neighbor City from the current location exists.
if(StartName==EndName) return true: If the destination and location are the same, job is finished and successful.
if(StartName == "" || EndName == "") return false: If the start or destination is non-existent, a search cannot be made and the
attempt is a failure.
for(CityNumber=Cities.begin();CityNumber<Cities.end();CityNumber++):For loop to parse through all elements in the
CurrentCity=*CityNumber: Extract element from Cities vector and place in CurrentCity.
if(CurrentCity.Name==StartName): Perform comparison between the initial location and the name in the Cities vector.
StartCity=CurrentCity: Create City structure with name of start location.
StartCityFound=true: Set flag indicating successful creation of start location.
if(StartCityFound==false) return false: Check to see if start location has been created, return failure if unsuccessful.
PathsTraveled.push_back(NewRecord): Initialize PathsTraveled vector with Start Location.
Frontier.push_back(StartCity): Initialize Frontier queue with Start Location.
while(!Frontier.empty() && GoalFound==false): Check until the Goal is found or all locations have been checked.
CurrentCity=Frontier.front(): Place element in front of Frontier queue in the CurrentCity structure.
Explored.push_back(CurrentCity): Place CurrentCity structure in Explored queue
Frontier.pop_front(): Remove front element from Frontier queue.
for(NeighborNumber=CurrentCity.Neighbors.begin();NeighborNumber<CurrentCity.Neighbors.end();NeighborNumber++):For loop to parse through all the Neighbors of CurrentCity.
CurrentNeighbor=*NeighborNumber: Create CurrentNeighbor with data from Neighbors vector.
if(GetChildCity(CurrentNeighbor, &ChildCity)==false) return false:ChildCity becomes the City structure
with the same name as the Neighbor under analysis. Exit routine if no match found - Database Error.
if(ChildCity.Name==EndName) GoalFound=true: Once we find the Goal location, it is not necessary to search any more cities.
However, we must complete the loop to update the PathsTraveled data structure.
AlreadyExplored=false: Preset Explored flag to failure.
ExploredCityNumber=Explored.begin(): Initialize ExploredCityNumber to first element in Explored queue.
while(AlreadyExplored==false && ExploredCityNumber<Explored.end()): Loop through all elements in Explored queue until
a match is found.
ExploredCity=*ExploredCityNumber: Extract data from Explored queue and place in ExploredCity.
if(ExploredCity.Name==ChildCity.Name) AlreadyExplored=true: Check to see if ChildCity has already been explored. Set
AlreadyExplored flag if it has.
ExploredCityNumber++: Move the index to the next location in Explored queue.
if(AlreadyExplored==false): Test to see if ChildCity was NOT in the Explored queue.
AlreadyInFrontier=false: Preset Frontier flag to failure.
FrontierCityNumber=Frontier.begin(): Initialize FrontierCityNumber to first element in Frontier queue.
while(AlreadyInFrontier==false && FrontierCityNumber<Frontier.end()): Loop through all elements in Frontier queue
until a match is found.
FrontierCity=*FrontierCityNumber: Extract data from Frontier queue and place in FrontierCity.
if(FrontierCity.Name==ChildCity.Name) AlreadyInFrontier=true: Check to see if ChildCity has already been placed in
the Frontier. Set the AlreadyInFrontier flag if it has.
FrontierCityNumber++: Move the index to the next location in the Frontier queue.
if(AlreadyExplored==false && AlreadyInFrontier==false): Test for Child NOT Explored and NOT in Frontier.
Frontier.push_back(ChildCity): Save Child in Frontier.
PathNumber=PathsTraveled.begin( ): Set Path Record iterator to beginning of array.
PathFound=false: Preset PathFound flag to Failure.
while(PathFound==false && PathNumber<PathsTraveled.end()): Loop Through all Paths in PathsTraveled vector until a
match is found.
TemporaryRecord=*PathNumber: Extract Path from PathsTraveled vector and place in TemporaryRecord.
if(TemporaryRecord.LastEntry == CurrentCity.Name): Check to see if CurrentCity is the Last Entry in the Path.
NewRecord.AddPath(TemporaryRecord, ChildCity, CurrentNeighbor): Call AddPath Member function to append Current Child to
PathsTraveled.push_back(NewRecord): Save path as new element in PathsTraveled.
PathFound=true: Set flag to break out of loop.
PathNumber++: Index to next element in PathsTraveled vector.
return GoalFound: Return success or failure.
In order to continue with this guide, and continue the discussion with
Printing the Path Record which is keeping track of our progression:
Press the Button below: