[solved]-Need Help Java Modify Bfsjava Program Listing 132 Find Minimum Spanning Tree Using Breadth Q39065271

Need help in java

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

Use the code listed in 13.2 and 13.3 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
640 CHAPTER 13 Graphs
LISTING 13.2 Continued
//————————————————————-
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 we?re done
for(int j=0; j vertexList[j].wasVisited = false;
} // end bfs()
//————————————————————-
Searches 641
LISTING 13.2 Continued
// 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 OFLISTING13.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
{
646 CHAPTER 13 Graphs
LISTING 13.3 Continued
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
Minimum Spanning Trees 647
LISTING 13.3 Continued
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 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
648 CHAPTER 13 Graphs
LISTING 13.3 Continued
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

Expert Answer

---

Answer to Need help in java Modify the bfs.java program (Listing 13.2) to find the minimum spanning tree using a breadth-first sea… . . .