Book name: Data Structures and Algorithms in Java, Second Edition

JAVA: 13.1 Modify the bfs.java program (Listing 13.2) to find the minimum spanning tree using a breadth-first search, rather than the depth-first search shown in mst.java (Listing 13.3). In main(), create a graph with 9 vertices and 12 edges, and find its minimum spanning tree.

Extra info:

Use the code listed in 13.2 below, thanks!

Listing 13.2:

// 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 } // ------------------------------------------------------------- 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 for(int k=0; k adjMat[j][k] = 0; theQueue = new Queue(); } // end constructor // ------------------------------------------------------------- public void addVertex(char lab) { vertexList[nVerts++] = new Vertex(lab); } // ------------------------------------------------------------- public void addEdge(int start, int end) { adjMat[start][end] = 1; adjMat[end][start] = 1; } // ------------------------------------------------------------- public void displayVertex(int v) { System.out.print(vertexList[v].label); } // ------------------------------------------------------------- public void bfs() // breadth-first search { // begin at vertex 0 vertexList[0].wasVisited = true; // mark it displayVertex(0); // display it theQueue.insert(0); // insert at tail int v2; 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 were done for(int j=0; j vertexList[j].wasVisited = false; } // end bfs() // ------------------------------------------------------------- // returns an unvisited vertex adj to v public int getAdjUnvisitedVertex(int v) { for(int j=0; j if(adjMat[v][j]==1 && vertexList[j].wasVisited==false) return j; return -1; } // end getAdjUnvisitedVertex() // ------------------------------------------------------------- } // end class Graph //////////////////////////////////////////////////////////////// class BFSApp { public static void main(String[] args) { Graph theGraph = new Graph(); theGraph.addVertex(A); // 0 (start for dfs) theGraph.addVertex(B); // 1 theGraph.addVertex(C); // 2 theGraph.addVertex(D); // 3 theGraph.addVertex(E); // 4 theGraph.addEdge(0, 1); // AB theGraph.addEdge(1, 2); // BC theGraph.addEdge(0, 3); // AD theGraph.addEdge(3, 4); // DE System.out.print(Visits: ); theGraph.bfs(); // breadth-first search System.out.println(); } // end main() } // end class BFSApp ////////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////

***************************************************************************************************************************

///////////////////////////////////////////////////END OF LISTING 13.2/////////////////////////////////////////////////////////////

***************************************************************************************************************************

Listing 13.3:

// mst.java // demonstrates minimum spanning tree // to run this program: C>java MSTApp //////////////////////////////////////////////////////////////// Minimum Spanning Trees 645 class StackX { private final int SIZE = 20; private int[] st; private int top; // ------------------------------------------------------------- public StackX() // constructor { st = new int[SIZE]; // make array top = -1; } // ------------------------------------------------------------- public void push(int j) // put item on stack { st[++top] = j; } // ------------------------------------------------------------- public int pop() // take item off stack { return st[top--]; } // ------------------------------------------------------------- public int peek() // peek at top of stack { return st[top]; } // ------------------------------------------------------------- public boolean isEmpty() // true if nothing on stack { return (top == -1); } // ------------------------------------------------------------- } // end class StackX //////////////////////////////////////////////////////////////// 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 StackX theStack; // ------------------------------------------------------------- public Graph() // constructor { vertexList = new Vertex[MAX_VERTS]; // adjacency matrix adjMat = new int[MAX_VERTS][MAX_VERTS]; nVerts = 0; for(int j=0; j for(int k=0; k adjMat[j][k] = 0; theStack = new StackX(); } // end constructor // ------------------------------------------------------------- public void addVertex(char lab) { vertexList[nVerts++] = new Vertex(lab); } // ------------------------------------------------------------- public void addEdge(int start, int end) { adjMat[start][end] = 1; adjMat[end][start] = 1; } // ------------------------------------------------------------- public void displayVertex(int v) { System.out.print(vertexList[v].label); } // ------------------------------------------------------------- public void mst() // minimum spanning tree (depth first) { // start at 0 vertexList[0].wasVisited = true; // mark it theStack.push(0); // push it 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 were done for(int j=0; j vertexList[j].wasVisited = false; } // end tree // ------------------------------------------------------------- // returns an unvisited vertex adj to v public int getAdjUnvisitedVertex(int v) { for(int j=0; j if(adjMat[v][j]==1 && vertexList[j].wasVisited==false) return j; return -1; } // end getAdjUnvisitedVertex() // ------------------------------------------------------------- } // end class Graph //////////////////////////////////////////////////////////////// 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(); // minimum spanning tree System.out.println(); } // end main() } // end class MSTApp ////////////////////////////////////////////////////////////////