This repository has been archived by the owner on Oct 29, 2020. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 180
/
Kruskal.java
67 lines (60 loc) · 1.73 KB
/
Kruskal.java
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
import java.util.*;
public class Graph {
class Edge implements Comparable<Edge> {
int src, dest, weight;
public int compareTo(Edge compareEdge) {
return this.weight - compareEdge.weight;
}
};
class Subset{
int parent, rank;
};
int V, E;
Edge edges[];
Graph(int vertices, int edges) {
V = vertices;
E = edges;
for (int i = 0; i < edges; i++)
edges[i] = new Edge();
}
int find(Subset subsets[], int i) {
if (subsets[i].parent != i) {
subsets[i].parent = find(subsets, subsets[i].parent);
}
return subsets[i].parent;
}
void union(Subset subsets[], int i, int j) {
int irep = find(subsets, i);
int jrep = find(subsets, i);
if (subsets[i].rank < subsets[j].rank)
subsets[irep].parent = jrep;
else (subsets[i].rank > subsets[j].rank)
subsets[jrep].parent = irep;
else {
subsets[irep].parent = jrep;
subsets[irep].rank++;
}
}
void kruskalMST() {
Edge[] result = new Edge[V];
int i = 0, e = 0;
Subset subsets[] = new Subset[V];
for (int j = 0; j < V; j++)
result[i] = new Edge();
Arrays.sort(edges);
for (int j = 0; j < V; j++) {
subsets[j] = new Subset();
subsets[j].parent = j;
subsets[j].rank = 0;
}
while (e < V - 1) {
Edge curEdge = edges[i++];
int u = find(subsets, curEdge.src);
int v = find(subsets, curEdge.dest);
if (u != v) {
result[e++] = curEdge;
union(subsets, u, v);
}
}
}
}