Book name: Data Structures and Algorithms in Java, Second Edition JAVA: 13.1 Mod
ID: 658278 • Letter: B
Question
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.
Explanation / Answer
class Queue
{
private final int SIZE = 20;
private int[] queArray;
private int front;
private int rear;
public Queue()
{
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.