Hi,

I just got assigned my last assignment for my data structures and algorithms in Java class this semester. This assignment is about graphs and I need help with one part. I have attached the assignment sheet and sample code that is needed to do this part.

Assignment:

Graph:

/* * demonstrates depth-first search (DFS), breath-first search (BFS), * and minimum spanning tree (MST) */ class Graph { private final int MAX_VERTS = 20; private Vertex vertexList[]; // list of vertices private int adjMat[][]; // adjacency matrix private int nVerts; // current number of vertices private Stack theStack; private Queue theQueue; //------------------------------------------------------------ public Graph() // constructor { vertexList = new Vertex[MAX_VERTS]; // adjacency matrix adjMat = new int[MAX_VERTS][MAX_VERTS]; nVerts = 0; for(int y=0; y

while( !theQueue.isEmpty() ) // until queue empty, { int v1 = theQueue.remove(); // remove vertex at head // until it has no unvisited neighbors while( (v2=getAdjUnvisitedVertex(v1)) != -1 ) { // get one, vertexList[v2].wasVisited = true; // mark it displayVertex(v2); // display it theQueue.insert(v2); // insert it } // end while } // end while(queue not empty)

// queue is empty, so we're done for(int j=0; j

while( !theStack.isEmpty() ) // until stack empty { // get stack top int currentVertex = theStack.peek(); // get next unvisited neighbor int v = getAdjUnvisitedVertex(currentVertex); if(v == -1) // if no more neighbors theStack.pop(); // pop it away else // got a neighbor { vertexList[v].wasVisited = true; // mark it theStack.push(v); // push it // display edge displayVertex(currentVertex); // from currentV displayVertex(v); // to v System.out.print(" "); } } // end while(stack not empty)

// stack is empty, so we're done for(int j=0; j

MSTApp:

public class MSTApp {

public static void main(String[] args) { Graph theGraph = new Graph(); theGraph.addVertex('A'); // 0 (start for mst) theGraph.addVertex('B'); // 1 theGraph.addVertex('C'); // 2 theGraph.addVertex('D'); // 3 theGraph.addVertex('E'); // 4

theGraph.addEdge(0, 1); // AB theGraph.addEdge(0, 2); // AC theGraph.addEdge(0, 3); // AD theGraph.addEdge(0, 4); // AE theGraph.addEdge(1, 2); // BC theGraph.addEdge(1, 3); // BD theGraph.addEdge(1, 4); // BE theGraph.addEdge(2, 3); // CD theGraph.addEdge(2, 4); // CE theGraph.addEdge(3, 4); // DE

System.out.print("Minimum spanning tree: "); theGraph.mst_dfs(); // minimum spanning tree (depth-first) System.out.println();

}

} //end class MSTApp

1. Modify the class Graph and add a method called mst_bfs to find the minimum spanning tree using breadth-first search. To test the method you defined, in the main() of class MSTApp, create a graph with 9 vertices and 12 edges and find it minimum spanningtree