Data Structures in C++ I need help with the bfs command.. Thank you.. Implement
ID: 3842425 • Letter: D
Question
Data Structures in C++
I need help with the bfs command.. Thank you..
Implement the following commands Command Description create n r Create a new empty graph in register r, with n nodes print r Print some representation of the graph in r arc a b r In the graph in register r, create an arc from node a to b biarc a b r Create a bidirectional arc from a to b in r bfs a b r Perform a breadth-first search from a to b in r, printing the distance Write the register commands necessary to create the following graph: alpha place them in a comment in your source code. What is the distance from node 9 to node 6?Explanation / Answer
Answer
Below is the function for bsf in c++ language:
void Graph::Breadth_First_Search(int s)
{
//first mark all the vertices as not visited, by assigning 0
bool *visited = new bool[V];
int i;
for(i = 0; i < V; i++)
visited[i] = false;
// then create a queue for Breadth_First_Search
list<int> queue;
// For the current node mark it as visited and enqueue it
visited[s] = true;
queue.pushBack(s);
// the updated value of 'i' will be used to get all adjacent vertices of a vertex
list<int>::iterator i;
while(!queue.empty())
{
// as the search progresses, dequeue a vertex from queue and print it
s = queue.front();
cout << s << " ";
queue.popFront();
// Access all the adjacent vertices of the dequeued vertex s
// If any of the adjacent has not been visited, then mark them visited
// and enqueue it
for(i = adj[s].begin(); i != adj[s].end(); ++i)
{
if(!visited[*i])
{
visited[*i] = true;
queue.pushBack(*i);
}
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.