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.

struct adjVertex{ vertex *v; };

struct vertex{ int value; bool visited; std::vector 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 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  Q; Q.push(start); start->visited = true; cout value //Students have to fill in this part  while (!Q.empty()) { vertex *node = Q.front(); Q.pop(); for (int i = 0; i adj.size(); i++) {  //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 } } } 

Example Input: 

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

Please use the following graphs for the testcases: