Hot-Link Menu in Right-Side Column

Last Updated 6-29-2010


C++ Depth-First Search Algorithm Function

It is now time to develop the code using the algorithm in Figure DFS-2. The following is the C++ code for peforming a C++ Depth-First Search algorithm:


//Perform Depth First Search giving Start Location and Ending Location

bool	DepthFirstSearch(string StartName, string EndName)
{	
	City		CurrentCity;
	City		StartCity;
	City		ChildCity;
	City		ExploredCity;
	City		FrontierCity;

	Neighbor	CurrentNeighbor;

	bool	StartCityFound=false;
	bool	GoalFound=false;
	bool	AlreadyExplored;
	bool	AlreadyInFrontier;
	bool	NewChildFound;
	bool	PathFound;

	vector<City>::iterator	CityNumber;

	deque<City>			Frontier;
	deque<City>			Explored;

	deque<City>::iterator	FrontierCityNumber;
	deque<City>::iterator	ExploredCityNumber;

	PathRecord				NewRecord(StartName);
	PathRecord				TemporaryRecord("");

	vector<PathRecord>::iterator	PathNumber;

	if(StartName==EndName) return true;

	if(StartName=="" || EndName == "") return false;

//*************************************************************************
//			Search For Start
//*************************************************************************

	for(CityNumber=Cities.begin();CityNumber<Cities.end();CityNumber++)
	{
		CurrentCity=*CityNumber;
		if(CurrentCity.Name==StartName)
		{
			StartCity=CurrentCity;
			StartCityFound=true;
		}
	}

	if(StartCityFound==false) return false;

	PathsTraveled.push_back(NewRecord);
	Frontier.push_back(StartCity);

//*************************************************************************
//			Search For Goal
//*************************************************************************

	cout<<"\nRecording Exploratory Process:\n"<<"Start Location: "<<
		StartName<<"\t Ending Location: "<<EndName<<endl;

//Get Next Location in the Frontier

	while(!Frontier.empty() && GoalFound==false)
	{
		CurrentCity=Frontier.back();
		cout<<"\nCurrent City: "<<CurrentCity.Name<<endl;
		NewChildFound=false;

//Look through the Neighbors until an explored City is found.

		while(CurrentCity.NeighborNumber<CurrentCity.Neighbors.end() && NewChildFound==false)
		{
			CurrentNeighbor=*CurrentCity.NeighborNumber;
			cout<<"Current Neighbor: "<<CurrentNeighbor.Name<<endl;
			if(GetChildCity(CurrentNeighbor, &ChildCity)==false) 
			{
				cout<<"Didn't find a child\n";
				return false;
			}
			if(ChildCity.Name==EndName) 
			{
				cout<<"Goal Found\n";
				GoalFound=true;
			}

//Check for Child Already Explored

			AlreadyExplored=false;
			ExploredCityNumber=Explored.begin();
			
			while(AlreadyExplored==false && ExploredCityNumber<Explored.end())
			{
				ExploredCity=*ExploredCityNumber;
				
				if(ExploredCity.Name==ChildCity.Name) AlreadyExplored=true;
				ExploredCityNumber++;
			}
			

//Check for Child Already in Frontier

			if(AlreadyExplored==false)
			{
				AlreadyInFrontier=false;
				FrontierCityNumber=Frontier.begin();
				
				while(AlreadyInFrontier==false && FrontierCityNumber<Frontier.end())
				{
					FrontierCity=*FrontierCityNumber;
					
					if(FrontierCity.Name==ChildCity.Name) AlreadyInFrontier=true;
					FrontierCityNumber++;
				}
				
			}

//Put the parent in the Frontier queue and Expand the Child Node
//Record the process in the Paths Traveled vector.

			if(AlreadyExplored==false && AlreadyInFrontier==false)
			{
				Frontier.push_back(ChildCity);
				NewChildFound=true;
				PathNumber=PathsTraveled.begin( );
				PathFound=false;
				while(PathFound==false && PathNumber<PathsTraveled.end( ))
				{
					TemporaryRecord=*PathNumber;
					if(TemporaryRecord.LastEntry==CurrentCity.Name)
					{
						NewRecord.AddPath(TemporaryRecord, 
							ChildCity, CurrentNeighbor);
						PathsTraveled.push_back(NewRecord);
						PathFound=true;
					}
					PathNumber++;
				}
			}
			
			CurrentCity.NeighborNumber++;
		}

//Display the Explored Queue on each pass

		if(NewChildFound==false) 
		{
			Explored.push_back(CurrentCity);
			Frontier.pop_back();
		}

		cout<<"Explored: ";
		
		for(ExploredCityNumber=Explored.begin();
			ExploredCityNumber<Explored.end();ExploredCityNumber++)
		{
			ExploredCity=*ExploredCityNumber;
			cout<<ExploredCity.Name<<" \t";
		}
		cout<<endl;

//Display the Frontier Queue on each pass

		cout<<"Frontier: ";
		for(FrontierCityNumber=Frontier.begin(); 
			FrontierCityNumber<Frontier.end();FrontierCityNumber++)
		{
			FrontierCity=*FrontierCityNumber;
			cout<<FrontierCity.Name<<" \t";
		}
		cout<<endl;
	}
	
	return GoalFound;
}


						

Figure DFS-11: Code Listing for Depth-First Search


The following listing describes the function of the Depth-First Search Code:

  • bool DepthFirstSearch(string StartName, string EndName): Declaration Statement

    • bool DepthFirstSearch: returns true (goal found) or false (failure to find goal.

    • string StartName: Text used to match start location.

    • string EndName: Goal Location.

  • City CurrentCity: Temporary City Variable used as container during parsing of Cities vector.

  • City StartCity: Temporary City Variable used to extract starting location from Cities vector.

  • City ChildCity: Temporary City Variable used to extract Child nodes from Cities vector.

  • City ExploredCity: Temporary City Variable used to compare nodes in Explored queue.

  • City FrontierCity: Temporary City Variable used to compare nodes in Frontier queue.

  • Neighbor CurrentNeighbor: Neighbor Container used to extract data from CurrrentCity.Neighbors vector.

  • bool StartCityFound=false: Flag used to indicate whether or not requested start position is in the available database.

  • bool GoalFound=false: Flag used to indicate whether or not the 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 Frontier.

  • bool NewChildFound: Flag used to indicate if the path to Neighbor City from the current location exists.

  • bool PathFound: Flag used to indicate if the path from the current location to the current Neighbor City exists.

  • vector<City>::iterator CityNumber: Iterator to parse through Cities vector.

  • deque<City> Frontier: Stack to coordinate expanding not fully explored 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 path being created. Used to transfer data to Paths Traveled vector.

  • PathRecord TemporaryRecord(""): Container used to extract data from Paths traveled vector.

  • vector<PathRecord>::iterator PathNumber: Iterator to parse through Paths traveled vector.

  • 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 City Structure

  • 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.back( ): Place element in back of Frontier queue in the CurrentCity structure.

  • Frontier.pop_back( ): Remove the back element from the Frontier queue.

  • Explored.push_back(CurrentCity): Place CurrentCity structure in Explored queue

  • NewChildFound=false: Set flag indicating we have found the deepest node and need to move back up.

  • while(CurrentCity.NeighborNumber<CurrentCity.Neighbors.end() && NewChildFound==false)
    • while while loop proceeding until all children have been explored.

  • CurrentNeighbor=*CurrentCity.NeighborNumber: Create CurrentNeighbor with data from Neighbors vector.

  • if(GetChildCity(CurrentNeighbor, &ChildCity)==false): ChildCity becomes the City with the same name as the Neighbor under analysis - exit if no match found - Database Error.

  • 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.

  • NewChildFound=true: Set flag that more nodes are to be expanded.

  • 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.

  • 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.

  • CurrentCity.NeighborNumber++: Index to next neighbor in current node.

  • return GoalFound: Return success or failure.

In order to continue with this guide, and start the discussion of Depth-First Search Print Goal Path and the associated C++ code to perform the operation: Press the Button below:


Home


Artificial Intelligence

Big O Notation

NP Completeness

Intelligent Agents


Problem Definition

Formulating Problems

Toy Problems

Vacuum World


8-Puzzle

8 Queens

The Knuth Sequence

Real World Problems

Route Finding Problems

Touring Problems

Traveling Salesperson Problem

VLSI Layout

Robot Navigation

Automatic Assembly Sequencing


Searching For Solutions


Frontier Node Expansion

Search Algorithm Infrastructure

Child Node Creation

Measuring Algorithm Performance


Uninformed Search Strategies

Breadth-First Search

Breadth-First Characteristics

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

Uniform-Cost Search


Depth-First Search

Depth-First C++ Solution

Depth-First Data Structure


Depth-First MakeMap()

Depth-First Display Data

Depth-First Initial Listing


Depth-First GetChildCity()

Depth-First Path Record


Depth-First Search Function


Depth-First PrintGoalPath()

Depth-First Main()

Depth-Limited Search


Iterative Depth Search

Bidirectional Search

Comparing Strategies


Informed Search Strategies

Greedy Best-First

A* Search


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