Modify the bfs.java program to find the minimum spanning tree using a breadth-first search, rather than the depth-first search. In main(), create a graph with 9 vertices and 12 edges, and find its minimum spanning tree.

Include a report with the problem statement, analysis, algorithm design, class prototype (class contract), program Input/Output, and tested results (analysis your result to see if it is correct).

// bfs.java

// demonstrates breadth-first search

// to run this program: C>java BFSApp //////////////////////////////////////////////////////////////// class Queue { private final int SIZE = 20; private int[] queArray; private int front; private int rear; // ------------------------------------------------------------- public Queue() // constructor { queArray = new int[SIZE]; front = 0; rear = -1; } // ------------------------------------------------------------- public void insert(int j) // put item at rear of queue { if(rear == SIZE-1) rear = -1; queArray[++rear] = j; } // ------------------------------------------------------------- public int remove() // take item from front of queue { int temp = queArray[front++]; if(front == SIZE) front = 0; return temp; Searches 639 14 0672324539 CH13 10/10/02 9:10 AM Page 639 } // ------------------------------------------------------------- public boolean isEmpty() // true if queue is empty { return ( rear+1==front || (front+SIZE-1==rear) ); } // ------------------------------------------------------------- } // end class Queue //////////////////////////////////////////////////////////////// class Vertex { public char label; // label (e.g. A) public boolean wasVisited; // ------------------------------------------------------------- public Vertex(char lab) // constructor { label = lab; wasVisited = false; } // ------------------------------------------------------------- } // end class Vertex //////////////////////////////////////////////////////////////// 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 Queue theQueue; // ------------------ public Graph() // constructor { vertexList = new Vertex[MAX_VERTS]; // adjacency matrix adjMat = new int[MAX_VERTS][MAX_VERTS]; nVerts = 0; for(int j=0; j