Write Code In Java Kruskal’s Algorithm Objective: Implement Kruskal’s algorithm
ID: 3683987 • Letter: W
Question
Write Code In Java
Kruskal’s Algorithm
Objective:
Implement Kruskal’s algorithm and run it on a weighted graph of your own creation. The algorithm is used to find the minimum spanning tree in a graph. This is a greedy algorithm that examines each edge of the graph and only keeps the connections that are the smallest while still keeping a connection to that node. For more information look here:
http://en.wikipedia.org/wiki/Kruskal%27s_algorithm
Demonstrate the algorithm works by printing out every edge with weights in your graph, and then printing out the minimum spanning tree.
Explanation / Answer
import java.util.InputMismatchException;
import java.util.Scanner;
public class Prims {
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 Prims(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() {
System.out.println("SOURCE : DESTINATION = WEIGHT");
for (int vertex = 2; vertex <= numberofvertices; vertex++) {
System.out.println(parent[vertex] + " : " + vertex + " = "
+ adjacencyMatrix[parent[vertex]][vertex]);
}
}
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");
number_of_vertices = scan.nextInt();
adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];
System.out.println("Enter the Weighted Matrix for the graph");
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;
}
}
}
Prims prims = new Prims(number_of_vertices);
prims.primsAlgorithm(adjacency_matrix);
prims.printMST();
} catch (InputMismatchException inputMismatch) {
System.out.println("Wrong Input Format");
}
scan.close();
}
}
===========
Sample
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.