(C++)Below are depthFirstTraversal, dft, and breadthFirstTraversal methods. Help

Question

(C++)Below are depthFirstTraversal, dft, and breadthFirstTraversal methods. Help create(implement) method named cycleFinder by follow this instruction: traverse the graph and determine the node(s) that start the cycle(s) in the graph. Use the unordered_map data structure in the STL to keep track of the nodes that have been visited.

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

Here the code, compile and check it. If any doubts post comments.

I used depth first search traversal.

Source Code:

#include<tr1/unordered_map>
using namespace std::tr1;

void graphType::cycleFinder()
{
unordered_map<int,bool> visited;
bool *temp_array=new bool[gSize];
for(int i=0;i<gSize;i++)
{
  visited[i]=false;
  temp_array[i]=false;
}

for(int i=0;i<gSize;i++)
{
  if (isCycle(i,visited,temp_array))
  {
   //Print the starting nodes of the cycle
   //only if there exists cycle.
   cout<<"Cycle found at start vertex: "<<i<<endl;
  }
}

}

//Recursive function to check if cycles exist.
bool graphType::isCycle(int i,unordered_map<int,bool> visited,bool *temp_array)
{
if (visited[i]==false)
{
  visited[i]=true;
  temp_array[i]=true;
  
  linkedListIterator itr;
  
  for(itr=graph[i].begin();itr!=graph[v].end();++itr)
  {
   if(!visited[*itr] && isCycle(*itr,visited,temp_array))
   return true;
   
   else if(temp_array[*itr])
   return true;
  }

}
temp_array[i]=false;
return false;
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.