JAVA: 13.1 Modify the bfs.java program (Listing 13.2) to find the minimum spanni
ID: 653968 • Letter: J
Question
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.
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.
Explanation / Answer
// 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;
}
// -------------------------------------------------------------
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.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.