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

Please find the commented code below. Please provide the supporting code of other methods to test the code

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 << " ";

    int maxAdjacent = 0;                        //Variable to keep count of maximum vertices of visited vertices
    vertex* vertexWithMaxAdjacentNodes;         //Vertex with maimum adjacent vertices
    while (!Q.empty()) {
        vertex *node = Q.front();
        Q.pop();

        if((int)node->adj.size() > maxAdjacent){        //If the current vertex has more adjacent vertices than the previous max
            vertexWithMaxAdjacentNodes = node;          //mark this vertex as the new max
        }

        for (int i = 0; i < (int)node->adj.size(); i++) {
            if (!((node->adj)[i]->v->visited))              //if the adjacent vertex is not visited before
            {
                ((node->adj)[i]->v->visited) = true;
                 Q.push((node->adj)[i]->v);                  //Push the adjacent vertex to the queue(standard BFS)
            }
        }
        cout << node->value << " ";                     //Print the BFS traversal
    }
    cout << "Node with max adjacent vertices : ">>vertexWithMaxAdjacentNodes->value>>endl; //Print details of max vertex after the BFS is printed
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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