The remaining nodes and connections will need to be entered. After which we begin the construct for the Depth-First
Search algorithm. A useful subroutine will be to search the database for the City class with the same name as the
Neighbors that we are
parsing through. Viewing our current position as the Parent, each Neighbor will be considered a Child. The function will be
called GetChildCity and will return a City class by reference. An empty search will return a false, indicating, at least for this application,
that we have an error in entering our database information.
//Function to return Success or Failure on finding the Child Node given the
//Parent is a structure of type Neighbor. The ChildCity is returned by reference.
bool GetChildCity(Neighbor Parent, City* ChildCity)
Figure DFS-9: Code Listing for GetChild
The following is a description of the functioning of the code:
bool GetChildCity(Neighbor Parent, City* ChildCity): Function declaration returning true or false.
Neighbor Parent: Neighbor containing the name of City class needed for analysis.
City* ChildCity: Pointer to City class data structure match returned with true.
City TempCity: Temporary City class data structure used to transfer data out of Cities vector.
vector<City>::iterator CityNumber: Index pointer to move through Cities vector.
Loop through all the elements in the Cities vector.
TempCity=*CityNumber: Transfer data from Cities vector into temporary City data structure.
if(TempCity.Name==Parent.Name): Comparison for match.
*ChildCity=TempCity: Transfer data from Temporary container to passed pointer.
return true: Indicate successful match found and data in passed pointer is valid.
return false: Indicate match was not found - error in database.
It will be necessary to keep track of the paths taken during progession
of the algorithm. The following class data
structure will record the progression made during the search process:
void AddPath(PathRecord, City, Neighbor);
void PathRecord::AddPath(PathRecord ParentRecord, City ChildCity, Neighbor CurrentNeighbor)
this->AccumulatedPath=ParentRecord.AccumulatedPath+" - "+ChildCity.Name;
Figure DFS-10: Class Data Structure to Record Paths Taken
The purpose of the Path Record class, is that we will need to keep
track of the cities that we have explored,
and how we got there. Let's go through an explanation of the code:
class PathRecord: Declaration of PathRecord class.
string AccumulatedPath: This will be the history of all cities we have visited to get to the current destination.
string LastEntry: When the current city we are evaluating matches the last entry - it means we are continuing that path.
int AccumulatedDistance: The distance we have accumulated from the start to our current position.
PathRecord(string): Constructor to create and initialize the PathRecord construct.
void AddPath(PathRecord, City, Neighbor): Add the current city we are exploring to the appropriate path.
PathRecord::PathRecord(string Start): Constructor/Initializer for the PathRecord construct.
AccumulatedPath=Start: The path we have traveled starts with the name of the beginning location.
LastEntry=Start: The path we have traveled ends with the name of the beginning location as well.
AccumulatedDistance=0: We have not moved yet, so our total distance is initially 0.
void PathRecord::AddPath(PathRecord ParentRecord, City ChildCity, Neighbor CurrentNeighbor): Function to Add the current
location to the path already traveled.
PathRecord ParentRecord: Record of Path already traveled to arrive at current location.
City ChildCity: Name of Current Location
Neighbor CurrentNeighbor: Construct containing distance between last location and current location.
this->AccumulatedPath=ParentRecord.AccumulatedPath+" - "+ChildCity.Name: Add Current location to path traveled.
this->LastEntry=ChildCity.Name: Change the Last Entry flag to the name of the current location.
this->AccumulatedDistance=ParentRecord.AccumulatedDistance+CurrentNeighbor.Distance: Add the distance between the last
location traversed and the current location to the distance already traveled.
vector<PathRecord> PathsTraveled: Each entry in PathsTraveled is a Record of each of the individual paths that have been
In order to continue with this guide, and start the discussion of
and the associated C++ code to perform the operation:
Press the Depth-First Search Algorithm Function Button below:
Big O Notation
The Knuth Sequence
Real World Problems
Route Finding Problems
Traveling Salesperson Problem
Automatic Assembly Sequencing
Searching For Solutions
Frontier Node Expansion
Search Algorithm Infrastructure
Child Node Creation
Measuring Algorithm Performance
Uninformed Search Strategies
C++ Breadth-First Search Code
Breadth-First Data Structure
Breadth-First Main Program
Breadth-First Make Map
Breadth-First Make Neighbor
Breadth-First Point of Origin
Breadth-First Print Cities
Breadth-First Initial Listing
Breadth-First Path Record
Breadth-First Get Child City
C++ Breadth-First Search Code
Breadth-First Print Goal Path
Depth-First C++ Solution
Depth-First Data Structure
Depth-First Display Data
Depth-First Initial Listing
Depth-First Path Record
Depth-First Search Function
Iterative Depth Search
Informed Search Strategies
Conditions For Optimality
Optimality of A*
C++ A* Search Code
A* Search Data Structure
A* Search Data Entry
A* Search GetChildCity()
C++ Min Priority Queue
C++ A* Search Code Function
C++ A* Headers & Prototypes
C++ A* Search Main()
Normalized Information Distance