(C++)Below are depthFirstTraversal, dft, and breadthFirstTraversal methods. Plea
ID: 3846253 • Letter: #
Question
(C++)Below are depthFirstTraversal, dft, and breadthFirstTraversal methods. Please help comment all lines (each code) and explain what it does and how it performs the method.
void graphType::depthFirstTraversal()
{
int index;
bool *visited;
visited=new bool[gSize];
for(index = 0; index < gSize; index++)
{
visited[index]=false;
}
for(index = 0; index < gSize; index++)
if(!visited[index])
dft(index, visited);
delete[] visited;
printGraph();
} //end depthFirstTraversal
void graphType::dft(int v, bool visited[])
{
visited[v] = true;
cout << " " << v << " ";
linkedListIterator mytp;
for(mytp=graph[v].begin(); mytp!=graph[v].end(); ++mytp)
{
int x = *mytp;
if(!visited[x])
dft(x,visited);
}
} //end dft
void graphType::breadthFirstTraversal()
{
int index;
linkedQueueType tp;
bool *visited;
visited = new bool[gSize];
for(index=0;index visited[index]=false;
linkedListIterator tt;
for(index=0; index
if(!visited[index])
{
tp.addQueue(index);
visited[index]=true;
cout << " " << index << " ";
while(!tp.isEmptyQueue())
{
int x = tp.front();
tp.deleteQueue();
for(tt=graph[x].begin();tt!=graph[x].end();++tt)
{
int y = *tt;
if(!visited[y])
{
tp.addQueue(y);
visited[y]=true;
cout<<" "<
} //end breadthFirstTraversal
Explanation / Answer
void graphType::depthFirstTraversal()
{
int index;//to store the position
bool *visited;//store the visited node
visited=new bool[gSize]; // assuming the size
for(index = 0; index < gSize; index++)//loops runs from 0 to the total graph size
{
visited[index]=false; //each time it assign the visited node to false
}
for(index = 0; index < gSize; index++)//same loop runs from 0 to the graph size
if(!visited[index]) //if the visitedone is not false
dft(index, visited); //function is called with index and the visited value
delete[] visited; //once node is visited it is removed
printGraph(); // it is uses to print the final graph
} //end depthFirstTraversal
void graphType::dft(int v, bool visited[])//two parametes for the index and the visited node
{
visited[v] = true; // it assign the index of the visited with true
cout << " " << v << " "; //print the index value
linkedListIterator mytp; //mytp of type linkedListIteratoer is created
for(mytp=graph[v].begin(); mytp!=graph[v].end(); ++mytp) //the loop runs from the beginning of the graph to the end
{
int x = *mytp; // stores the addres of the current node
if(!visited[x]) //again checks with value whether it is visited or not
dft(x,visited); // based on it calls it again
}
} //end dft
void graphType::breadthFirstTraversal()
{
int index; //to store the position
linkedQueueType tp; //datatype of type linkedQueueType
bool *visited; //to store the status of the node
visited = new bool[gSize]; //size is created
for(index=0;index visited[index]=false; //loop runs for making the visited node false
linkedListIterator tt; // datatype of linkedListIteratoer is created
for(index=0; index
if(!visited[index]) //it checks with the current boolean value of the node
{
tp.addQueue(index); //it adds to the addqueue by passing the value
visited[index]=true;
cout << " " << index << " ";// prints the index value
while(!tp.isEmptyQueue()) //checks with the empty condition
{
int x = tp.front(); //if satisfied it brought to the front of the queue
tp.deleteQueue(); //deleteQueue function is called
for(tt=graph[x].begin();tt!=graph[x].end();++tt)//loop runs from the beginning till the end of the graph
{
int y = *tt; //stores the pointer address
if(!visited[y]) //check with value of the visited
{
tp.addQueue(y); //element is passed to the addqueue function
visited[y]=true;//value of the visited node is made true
cout<<" "<//to print a whitespace
} //end breadthFirstTraversal
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.