Write a method that prints the vertices in a graph visited in a breadth-first se

Question

Write a method that prints the vertices in a graph visited in a breadth-first search (BFS) and the vertex with the maximum number of adjacent nodes.

You need to fill in the appropriate code in the following function, which has already been defined for you. Copy the code provided into the coding window as the starting point for your answer.

void Graph::findNodeWithMaximumAdjacent(int startVertex);

The function should print the BFS sequence and the node that has maximum number of adjacent nodes

The vertex structure includes a "visited" variable, set to false by default.

Testcase 1: findNodeWithMaximumAdjacent(10);

Output: 10 25 35 40

Node with max adjacent vertices : 25

Explanation: 10 is the starting vertex. 25 and 35 are its adjacent vertices, and 40 is adjacent to 25. In the next iteration, all of the nodes in the queue would have been visited and hence we don't have any other nodes to print. Node 25 is selected as the node with maximum adjacent vertices because Node 25 has 3 adjacent nodes whereas other nodes have lesser adjacent vertices

Explanation / Answer

struct adjVertex{
vertex *v;
};
struct vertex{
int value;
bool visited;
std::vector<adjVertex> adj;
};
Here is the definition of the Graph class:

class Graph
{
public:
Graph();
~Graph();
void addEdge(int v1, int v2);
void addVertex(int name);
void displayEdges();
void findNodeWithMaximumAdjacent(int startVertex);
private:
std::vector<vertex> vertices;
};
Use this function definition and fill in the blanks to complete the function.

void Graph::findNodeWithMaximumAdjacent(int startVertex) {
vertex *start;
for (int i = 0; i < (int)vertices.size(); i++) {
vertices[i].visited = false;
if (vertices[i].value == startVertex) {
start = &vertices[i];
}
}
queue<vertex*> Q;
Q.push(start);
start->visited = true;
cout << start->value << " ";
//Students have to fill in this part
vertex *maximumAdjacent;
while (!Q.empty()) {
vertex *node = Q.front();
cout<<node->value<<" "; // print the current visiting node value
Q.pop();
if(!maximumAdjacent) // if maximumAdjacent is not set
maximumAdjacent=node; // set maximumAdjacent to the current node
else if((int)node->adj.size()>(int)maximumAdjacent->adj.size()) // if size of node's adjacency list is greater
maximumAdjacent=node; // set maximumAdjacent to the current node
for (int i = 0; i < (int)node->adj.size(); i++) {
vertex *v=(node->adj[i]).v; // current adjacent node of the visited node
if(v->visited==false) // if adjacent node is not visited
{
v->visited=true; // set the adjacent node as visited to avoid other nodes from adding it to queue again
Q.push(v); // push the adjacent node in the Q
}
//Students have to fill in this part of the code and you can print the output within the loop as well as outside the loop

}
}
cout<<endl<<"Node with maximum adjacent vertices: "<<maximumAdjacent->value<<endl; // print the maximumAdjacent node value
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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