Write a method that is part of a class for a graph implemented as an adjacency matrix. The method takes the ID of the starting vertex as input and performs a breadth first search. The output is the list of vertices in breadth first search order.

Breadth first search is not unique. We need unique answers so we can test. So for this implementation, all ties are broken by choosing the vertex whose ID has the lowest numerical value.

Input cases are posed as the number of edges followed by the end vertices for each edge. We will read in the edges and place them into an adjacency matrix. We will then call a breadth first search method that you will implement. The output from the method should be a print out of the list of vertices in breadth first search order.

Sample Input 1:

8 1 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 

Sample Output 1:

1 2 3 4 5 6 7 8 9 

Sample Input 2:

7 2 1 3 2 6 3 5 3 4 3 4 1 6 2 

Sample Output 2:

1 2 4 3 6 5

#include #include

class My_Graph { const static int MAXNUMVERTICES = 100; int theGraph[MAXNUMVERTICES][MAXNUMVERTICES]; bool undirected; public:

My_Graph() { undirected = true; }

void insertEdge(int to, int from, int weight) { theGraph[to][from] = weight; theGraph[from][to] = weight; } void breadthFirstSearch(int start) { //your code here

} };

int main() { My_Graph *theGraph = new My_Graph(); int numEdges, inVert, outVert; int lowestVert=999; std::cin >> numEdges; for (int i=0; i> inVert; std::cin >> outVert; theGraph->insertEdge(inVert, outVert, 1); if (inVert < lowestVert) lowestVert = inVert; if (outVert < lowestVert) lowestVert = outVert; } theGraph->breadthFirstSearch(lowestVert); }