⬅ Kruskal's Algorithm | A Helpful Line-by-Line Code Tutorial | Part 1

Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.

import java.util.Scanner;

public class kruskal{
	
	public static void main(String[] args){
		
		Scanner scan = new Scanner(System.in);
		int[][] matrix = new int[5][5];
		int[] parent = new int[5];
		int min;
		int u = 0; 
		int v = 0;
		int noOfEdges = 1;
		int total = 0;
		
		for(int i = 0; i < 5; i++){
			
			parent[i] = 0;
			
			for(int j = 0; j < 5; j++){
				
				matrix[i][j] = scan.nextInt();
				if(matrix[i][j]==0){
					matrix[i][j] = 999;
				}
				
			}
			
		}
		
		while(noOfEdges < 5){
			
			min = 999;
			
			for(int i = 0; i < 5; i++){
				
				for(int j = 0; j < 5; j++){
					
					if(matrix[i][j] < min){
						
						min = matrix[i][j];
						u = i;
						v = j;
						
					}
					
				}
				
			}
			
			while(parent[u]!=0){
				u = parent[u];
			}
			
			while(parent[v]!=0){
				v = parent[v];
			}
			
			if(v!=u){
				
				noOfEdges++;
				System.out.println("Edge Found: " + u + "->" + v+" Min : " + min);
				total+=min;
				parent[v] = u;
				
			}
			
			matrix[u][v] = 999;
			matrix[v][u] = 999;
			
		}
		
		System.out.println("The weight of the minimum spanning tree is "+total);
		
	}
	
}