JAVA: 13.1 Modify the bfs.java program (Listing 13.2) to find the minimum spanni
ID: 3684328 • 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. ?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 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
{
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
////////////////////////////////////////////////////////////////
Compare the MST of your running result of BFS with DFS in your report.
Explanation / Answer
The following two programs will help you to find the minimum spanning tree.
Programme 1:
// Program for to Traverse a Graph using BFS
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class BFS
{
private Queue<Integer> queue;
public BFS()
{
queue = new LinkedList<Integer>();
}
public void bfs(int adjacency_matrix[][], int source)
{
int number_of_nodes = adjacency_matrix[source].length - 1;
int[] visited = new int[number_of_nodes + 1];
int i, element;
visited[source] = 1;
queue.add(source);
while (!queue.isEmpty())
{
element = queue.remove();
i = element;
System.out.print(i + " ");
while (i <= number_of_nodes)
{
if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
{
queue.add(i);
visited[i] = 1;
}
i++;
}
}
}
public static void main(String... arg)
{
int number_no_nodes, source;
Scanner scanner = null;
try
{
System.out.println("Enter the number of nodes in the graph");
scanner = new Scanner(System.in);
number_no_nodes = scanner.nextInt();
int adjacency_matrix[][] = new int[number_no_nodes + 1][number_no_nodes + 1];
System.out.println("Enter the adjacency matrix");
for (int i = 1; i <= number_no_nodes; i++)
for (int j = 1; j <= number_no_nodes; j++)
adjacency_matrix[i][j] = scanner.nextInt();
System.out.println("Enter the source for the graph");
source = scanner.nextInt();
System.out.println("The BFS traversal of the graph is ");
BFS bfs = new BFS();
bfs.bfs(adjacency_matrix, source);
} catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input Format");
}
scanner.close();
}
}
Output:
$javac BFS.java
$java BFS
Enter the number of nodes in the graph
4
Enter the adjacency matrix
0 1 0 1
0 0 1 0
0 1 0 1
0 0 0 1
Enter the source for the graph
1
The BFS traversal of the graph is
1 2 4 3
Program 2:
//Java Program to Traverse Graph using DFS
import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.Stack;
public class DFS
{
private Stack<Integer> stack;
public DFS()
{
stack = new Stack<Integer>();
}
public void dfs(int adjacency_matrix[][], int source)
{
int number_of_nodes = adjacency_matrix[source].length - 1;
int visited[] = new int[number_of_nodes + 1];
int element = source;
int i = source;
System.out.print(element + " ");
visited[source] = 1;
stack.push(source);
while (!stack.isEmpty())
{
element = stack.peek();
i = element;
while (i <= number_of_nodes)
{
if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
{
stack.push(i);
visited[i] = 1;
element = i;
i = 1;
System.out.print(element + " ");
continue;
}
i++;
}
stack.pop();
}
}
public static void main(String...arg)
{
int number_of_nodes, source;
Scanner scanner = null;
try
{
System.out.println("Enter the number of nodes in the graph");
scanner = new Scanner(System.in);
number_of_nodes = scanner.nextInt();
int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
System.out.println("Enter the adjacency matrix");
for (int i = 1; i <= number_of_nodes; i++)
for (int j = 1; j <= number_of_nodes; j++)
adjacency_matrix[i][j] = scanner.nextInt();
System.out.println("Enter the source for the graph");
source = scanner.nextInt();
System.out.println("The DFS Traversal for the graph is given by ");
DFS dfs = new DFS();
dfs.dfs(adjacency_matrix, source);
}catch(InputMismatchException inputMismatch)
{
System.out.println("Wrong Input format");
}
scanner.close();
}
}
Output:
$javac DFS.java
$java DFS
Enter the number of nodes in the graph
4
Enter the adjacency matrix
0 1 0 1
0 0 1 0
0 1 0 1
0 0 0 1
Enter the source for the graph
1
The DFS Traversal for the graph is given by
1 2 3 4
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.