# Java Program for Kruskal's algorithm using Union-Find algorithm

0 like 0 dislike
206 views

Find Minimum Cost Spanning Tree of a given connected undirected graph using Kruskal'salgorithm. Use Union-Find algorithms in your program

### For Indian Students- INR 570/- || For International Students- \$12.99/-

S.No.

Course Name

Apply Coupon

1.

Tensorflow 2 & Keras:Deep Learning & Artificial Intelligence

Apply Coupon

2.

Computer Vision with OpenCV | Deep Learning CNN Projects

Apply Coupon

3.

Complete Machine Learning & Data Science with Python Apply Coupon

4.

Natural Language Processing-NLP with Deep Learning in Python Apply Coupon

5.

Computer Vision OpenCV Python | YOLO| Deep Learning in Colab Apply Coupon

6.

Complete Python Programming from scratch with Projects Apply Coupon

0 like 0 dislike
by Goeduhub's Expert (5.8k points)

## For Theory of Kruskal's Algorithm Click here

Java Program

import java.util.*;

import java.lang.*;

import java.io.*;

class Kruk

// A class to represent a graph edge

class Edge implements Comparable<Edge>

int src, dest, weight;

public int compareTo(Edge compareEdge)

return this.weight-compareEdge.weight;

};

// A class to represent a subset for union-find

class subset

int parent, rank;

};

int V, E; // V-> no. of vertices & E->no.of edges

Edge edge[]; // collection of all edges

// Creates a graph with V vertices and E edges

Kruk(int v, int e)

V = v;

E = e;

edge = new Edge[E];

for (int i=0; i<e; ++i)

edge[i] = new Edge();

// A utility function to find set of an element i

int find(subset subsets[], int i)

// find root and make root as parent of i (path compression)

if (subsets[i].parent != i)

subsets[i].parent = find(subsets, subsets[i].parent);

return subsets[i].parent;

// A function that does union of two sets of x and y

void Union(subset subsets[], int x, int y)

int xroot = find(subsets, x);

int yroot = find(subsets, y);

// Attach smaller rank tree under root of high rank tree

if (subsets[xroot].rank < subsets[yroot].rank)

subsets[xroot].parent = yroot;

else if (subsets[xroot].rank > subsets[yroot].rank)

subsets[yroot].parent = xroot;

// If ranks are same, then make one as root and increment its rank by one

else

subsets[yroot].parent = xroot;

subsets[xroot].rank++;

void KruskalMST()

Edge result[] = new Edge[V]; // Tnis will store the resultant MST

int e = 0; // An index variable, used for result[]

int i = 0; // An index variable, used for sorted edges

for (i=0; i<V; ++i)

result[i] = new Edge();

Arrays.sort(edge);

// Allocate memory for creating V subsets

subset subsets[] = new subset[V];

for(i=0; i<V; ++i)

subsets[i]=new subset();

// Create V subsets with single elements

for (int v = 0; v < V; ++v)

subsets[v].parent = v;

subsets[v].rank = 0;

i = 0; // Index used to pick next edge

// Number of edges to be taken is equal to V-1

while (e < V - 1)

// Step 2: Pick the smallest edge. And increment

// the index for next iteration

Edge next_edge = new Edge();

next_edge = edge[i++];

int x = find(subsets, next_edge.src);

int y = find(subsets, next_edge.dest);

// If including this edge does't cause cycle,

// include it in result and increment the index

// of result for next edge

if (x != y)

result[e++] = next_edge;

Union(subsets, x, y);

// Else discard the next_edge

// print the contents of result[] to display

// the built MST

System.out.println("Edges of the constructed MST:");

for (i = 0; i < e; ++i)

System.out.println(result[i].src+" - " +

result[i].dest+" == " + result[i].weight);

public static void main (String[] args)

int V = 4; // Number of vertices in graph

int E = 5; // Number of edges in graph

Kruk graph = new Kruk(V, E);

// add edge 0-1

graph.edge[0].src = 0;

graph.edge[0].dest = 1;

graph.edge[0].weight = 10;

// add edge 0-2

graph.edge[1].src = 0;

graph.edge[1].dest = 2;

graph.edge[1].weight = 6;

// add edge 0-3

graph.edge[2].src = 0;

graph.edge[2].dest = 3;

graph.edge[2].weight = 5;

// add edge 1-3

graph.edge[3].src = 1;

graph.edge[3].dest = 3;

graph.edge[3].weight = 15;

// add edge 2-3

graph.edge[4].src = 2;

graph.edge[4].dest = 3;

graph.edge[4].weight = 4;

graph.KruskalMST();

Output