Write a Java, program that: Implements Prim’s algorithm for finding the minimum

Question

Write a Java, program that:

Implements Prim’s algorithm for finding the minimum spanning tree of a weighted graph. Your program should conform to the following specifications.

Prompt the user for the number of vertices in the graph.

Prompt the user to enter the adjacency matrix of the graph one row at a time.

Print the adjacency matrix of the graph.

Print the weight of the minimum spanning tree.

Print the list of edges in the minimum spanning tree.

Test the above program on the graph from problem #2

2. Use Prim's algorithm (Algorithm 4.1) to find a minimum spanni the following graph. Show the actions step by step. 32 01 17 45 18 10 28 25 59 4 12

Explanation / Answer

import java.util.InputMismatchException;
import java.util.Scanner;

public class Main
{
private boolean unsettled[];
private boolean settled[];
private int numberofvertices;
private int adjacencyMatrix[][];
private int key[];
public static final int INFINITE = 999;
private int parent[];

public Main(int numberofvertices)
{
this.numberofvertices = numberofvertices;
unsettled = new boolean[numberofvertices + 1];
settled = new boolean[numberofvertices + 1];
adjacencyMatrix = new int[numberofvertices + 1][numberofvertices + 1];
key = new int[numberofvertices + 1];
parent = new int[numberofvertices + 1];
}

public int getUnsettledCount(boolean unsettled[])
{
int count = 0;
for (int index = 0; index < unsettled.length; index++)
{
if (unsettled[index])
{
count++;
}
}
return count;
}

public void primsAlgorithm(int adjacencyMatrix[][])
{
int evaluationVertex;
for (int source = 1; source <= numberofvertices; source++)
{
for (int destination = 1; destination <= numberofvertices; destination++)
{
this.adjacencyMatrix[source][destination] = adjacencyMatrix[source][destination];
}
}

for (int index = 1; index <= numberofvertices; index++)
{
key[index] = INFINITE;
}
key[1] = 0;
unsettled[1] = true;
parent[1] = 1;

while (getUnsettledCount(unsettled) != 0)
{
evaluationVertex = getMimumKeyVertexFromUnsettled(unsettled);
unsettled[evaluationVertex] = false;
settled[evaluationVertex] = true;
evaluateNeighbours(evaluationVertex);
}
}

private int getMimumKeyVertexFromUnsettled(boolean[] unsettled2)
{
int min = Integer.MAX_VALUE;
int node = 0;
for (int vertex = 1; vertex <= numberofvertices; vertex++)
{
if (unsettled[vertex] == true && key[vertex] < min)
{
node = vertex;
min = key[vertex];
}
}
return node;
}

public void evaluateNeighbours(int evaluationVertex)
{

for (int destinationvertex = 1; destinationvertex <= numberofvertices; destinationvertex++)
{
if (settled[destinationvertex] == false)
{
if (adjacencyMatrix[evaluationVertex][destinationvertex] != INFINITE)
{
if (adjacencyMatrix[evaluationVertex][destinationvertex] < key[destinationvertex])
{
key[destinationvertex] = adjacencyMatrix[evaluationVertex][destinationvertex];
parent[destinationvertex] = evaluationVertex;
}
unsettled[destinationvertex] = true;
}
}
}
}

public void printMST()
{
int totalWeight=0;
System.out.println("Edges of the minimum spanning tree are ");   
System.out.println("SOURCE : DESTINATION = WEIGHT");
for (int vertex = 2; vertex <= numberofvertices; vertex++)
{
System.out.println(parent[vertex] + " : " + vertex +" = "+ adjacencyMatrix[parent[vertex]][vertex]);
totalWeight=totalWeight+adjacencyMatrix[parent[vertex]][vertex];
}
System.out.println("Weight of the spanning tree is "+ totalWeight);
}

public static void main(String... arg)
{
int adjacency_matrix[][];
int number_of_vertices;
Scanner scan = new Scanner(System.in);

try
{
System.out.println("Enter the number of vertices in the graph");
number_of_vertices = scan.nextInt();
adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];

System.out.println("Enter the adjacency matrix of the graph one row at a time.");
for (int i = 1; i <= number_of_vertices; i++)
{
for (int j = 1; j <= number_of_vertices; j++)
{
adjacency_matrix[i][j] = scan.nextInt();
if (i == j)
{
adjacency_matrix[i][j] = 0;
continue;
}
if (adjacency_matrix[i][j] == 0)
{
adjacency_matrix[i][j] = INFINITE;
}
}
}
System.out.println("Adjacency matrix is :");
for (int i = 1; i <= number_of_vertices; i++)
{
for (int j = 1; j <= number_of_vertices; j++)
{
System.out.print(adjacency_matrix[i][j]+" ");
}
System.out.println();
}

Prims prims = new Prims(number_of_vertices);
prims.primsAlgorithm(adjacency_matrix);
prims.printMST();

} catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input Format");
}
scan.close();
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.