forked from DhanushNehru/Hacktoberfest2025
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathKruskalAlgorithm.java
More file actions
85 lines (68 loc) · 2.32 KB
/
KruskalAlgorithm.java
File metadata and controls
85 lines (68 loc) · 2.32 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import java.util.*;
class KruskalAlgorithm {
static class Edge {
int source, destination, weight;
public Edge(int source, int destination, int weight) {
this.source = source;
this.destination = destination;
this.weight = weight;
}
}
static class Subset {
int parent, rank;
}
static int find(Subset[] subsets, int i) {
if (subsets[i].parent != i) {
subsets[i].parent = find(subsets, subsets[i].parent);
}
return subsets[i].parent;
}
static void union(Subset[] subsets, int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank) {
subsets[xroot].parent = yroot;
} else if (subsets[xroot].rank > subsets[yroot].rank) {
subsets[yroot].parent = xroot;
} else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
static void kruskalMST(Edge[] edges, int V, int E) {
Arrays.sort(edges, Comparator.comparingInt(e -> e.weight));
Edge[] result = new Edge[V - 1]; // The MST will have V-1 edges
int e = 0;
int i = 0;
Subset[] subsets = new Subset[V];
for (int v = 0; v < V; ++v) {
subsets[v] = new Subset();
subsets[v].parent = v;
subsets[v].rank = 0;
}
while (e < V - 1) {
Edge nextEdge = edges[i++];
int x = find(subsets, nextEdge.source);
int y = find(subsets, nextEdge.destination);
if (x != y) {
result[e++] = nextEdge;
union(subsets, x, y);
}
}
System.out.println("Edges in the Minimum Spanning Tree:");
for (int j = 0; j < e; ++j) {
System.out.println("Edge: " + result[j].source + " - " + result[j].destination + " with weight " + result[j].weight);
}
}
public static void main(String[] args) {
int V = 4;
int E = 5;
Edge[] edges = new Edge[E];
edges[0] = new Edge(0, 1, 10);
edges[1] = new Edge(0, 2, 6);
edges[2] = new Edge(0, 3, 5);
edges[3] = new Edge(1, 3, 15);
edges[4] = new Edge(2, 3, 4);
kruskalMST(edges, V, E);
}
}