This Java program to find mst using kruskal’s algorithm.Kruskal’s algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized
Here is the source code of the Java program to find mst using kruskal’s algorithm. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.
import java.util.Collections; import java.util.Comparator; import java.util.LinkedList; import java.util.List; import java.util.Scanner; import java.util.Stack; public class KruskalAlgorithm { private List<Edge> edges; private int numberOfVertices; public static final int MAX_VALUE = 999; private int visited[]; private int spanning_tree[][]; public KruskalAlgorithm(int numberOfVertices) { this.numberOfVertices = numberOfVertices; edges = new LinkedList<Edge>(); visited = new int[this.numberOfVertices + 1]; spanning_tree = new int[numberOfVertices + 1][numberOfVertices + 1]; } public void kruskalAlgorithm(int adjacencyMatrix[][]) { boolean finished = false; for (int source = 1; source <= numberOfVertices; source++) { for (int destination = 1; destination <= numberOfVertices; destination++) { if (adjacencyMatrix[destination] != MAX_VALUE && source != destination) { Edge edge = new Edge(); edge.sourcevertex = source; edge.destinationvertex = destination; edge.weight = adjacencyMatrix[destination]; adjacencyMatrix[destination] = MAX_VALUE; edges.add(edge); } } } Collections.sort(edges, new EdgeComparator()); CheckCycle checkCycle = new CheckCycle(); for (Edge edge : edges) { spanning_tree[edge.sourcevertex][edge.destinationvertex] = edge.weight; spanning_tree[edge.destinationvertex][edge.sourcevertex] = edge.weight; if (checkCycle.checkCycle(spanning_tree, edge.sourcevertex)) { spanning_tree[edge.sourcevertex][edge.destinationvertex] = 0; spanning_tree[edge.destinationvertex][edge.sourcevertex] = 0; edge.weight = -1; continue; } visited[edge.sourcevertex] = 1; visited[edge.destinationvertex] = 1; for (int i = 0; i < visited.length; i++) { if (visited[i] == 0) { finished = false; break; } else { finished = true; } } if (finished) break; } System.out.println("The spanning tree is "); for (int i = 1; i <= numberOfVertices; i++) System.out.print("\t" + i); System.out.println(); for (int source = 1; source <= numberOfVertices; source++) { System.out.print(source + "\t"); for (int destination = 1; destination <= numberOfVertices; destination++) { System.out.print(spanning_tree[destination] + "\t"); } System.out.println(); } } public static void main(String... arg) { int adjacency_matrix[][]; int number_of_vertices; Scanner scan = new Scanner(System.in); 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] = MAX_VALUE; } } } KruskalAlgorithm kruskalAlgorithm = new KruskalAlgorithm(number_of_vertices); kruskalAlgorithm.kruskalAlgorithm(adjacency_matrix); scan.close(); } } class Edge { int sourcevertex; int destinationvertex; int weight; } class EdgeComparator implements Comparator<Edge> { @Override public int compare(Edge edge1, Edge edge2) { if (edge1.weight < edge2.weight) return -1; if (edge1.weight > edge2.weight) return 1; return 0; } } class CheckCycle { private Stack<Integer> stack; private int adjacencyMatrix[][]; public CheckCycle() { stack = new Stack<Integer>(); } public boolean checkCycle(int adjacency_matrix[][], int source) { boolean cyclepresent = false; int number_of_nodes = adjacency_matrix.length - 1; adjacencyMatrix = new int[number_of_nodes + 1][number_of_nodes + 1]; for (int sourcevertex = 1; sourcevertex <= number_of_nodes; sourcevertex++) { for (int destinationvertex = 1; destinationvertex <= number_of_nodes; destinationvertex++) { adjacencyMatrix[sourcevertex][destinationvertex] = adjacency_matrix[sourcevertex[destinationvertex]; } } int visited[] = new int[number_of_nodes + 1]; int element = source; int i = source; visited = 1; stack.push(source); while (!stack.isEmpty()) { element = stack.peek(); i = element; while (i <= number_of_nodes) { if (adjacencyMatrix[element][i] >= 1 && visited[i] == 1) { if (stack.contains(i)) { cyclepresent = true; return cyclepresent; } } if (adjacencyMatrix[element][i] >= 1 && visited[i] == 0) { stack.push(i); visited[i] = 1; adjacencyMatrix[element][i] = 0;// mark as labelled; adjacencyMatrix[i][element] = 0; element = i; i = 1; continue; } i++; } stack.pop(); } return cyclepresent; } }
$javac KruskalAlgorithm.java $java KruskalAlgorithm Enter the number of vertices 6 Enter the Weighted Matrix for the graph 0 6 8 6 0 0 6 0 0 5 10 0 8 0 0 7 5 3 6 5 7 0 0 0 0 10 5 0 0 3 0 0 3 0 3 0 The spanning tree is 1 2 3 4 5 6 1 0 6 0 0 0 0 2 6 0 0 5 0 0 3 0 0 0 7 0 3 4 0 5 7 0 0 0 5 0 0 0 0 0 3 6 0 0 3 0 3 0
Related posts:
Interface trong Java 8 – Default method và Static method
Kết hợp Java Reflection và Java Annotations
Hướng dẫn sử dụng Printing Service trong Java
REST Web service: Upload và Download file với Jersey 2.x
String Processing with Apache Commons Lang 3
Java Program to Implement Karatsuba Multiplication Algorithm
Spring Boot Tutorial – Bootstrap a Simple Application
Different Ways to Capture Java Heap Dumps
Spring Boot - Servlet Filter
Java Program to find the peak element of an array using Binary Search approach
Java Program to Implement Bubble Sort
A Comparison Between Spring and Spring Boot
Java Program to Implement Knight’s Tour Problem
Java Program to Implement Fibonacci Heap
Cơ chế Upcasting và Downcasting trong java
Java Program to Perform Finite State Automaton based Search
Java Program to Implement Range Tree
Sử dụng Fork/Join Framework với ForkJoinPool trong Java
Tiêu chuẩn coding trong Java (Coding Standards)
Converting a List to String in Java
Spring 5 and Servlet 4 – The PushBuilder
Introduction to Netflix Archaius with Spring Cloud
Spring Boot - Tomcat Port Number
Java Program to Implement LinkedBlockingDeque API
Guide to Java Instrumentation
HttpClient with SSL
RestTemplate Post Request with JSON
Java Program to Implement Affine Cipher
Spring Boot Actuator
Java Program to Compute DFT Coefficients Directly
Mapping a Dynamic JSON Object with Jackson
Java Program to implement Dynamic Array