import java.util.
Scanner;
class Edge {
int src, dest, weight;
public Edge(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
}
class KruskalAlgorithm {
private int V; Number of vertices
private int E; Number of edges
private Edge[] edges; Array of edges
private int edgeCount = 0;
public KruskalAlgorithm(int v, int edgeCount) {
V = v;
E = edgeCount;
edges = new Edge[edgeCount];
}
public void addEdge(int src, int dest, int weight) {
edges[edgeCount++] = new Edge(src, dest, weight);
}
private int findParent(int[] parent, int vertex) {
if (parent[vertex] != vertex) {
parent[vertex] = findParent(parent, parent[vertex]); Path compression
}
return parent[vertex];
}
private void union(int[] parent, int[] rank, int x, int y) {
int rootX = findParent(parent, x);
int rootY = findParent(parent, y);
if (rootX != rootY) {
if (rank[rootX] rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
private void sortEdges() {
for (int i = 0; i E; i++) {
for (int j = 0; j E - i - 1; j++) {
if (edges[j].weight edges[j + 1].weight) {
Edge temp = edges[j];
edges[j] = edges[j + 1];
edges[j + 1] = temp;
}
}
}
}
public void KruskalsMST() {
sortEdges();
int[] parent = new int[V];
int[] rank = new int[V];
for (int i = 0; i V; i++) {
parent[i] = i;
rank[i] = 0;
}
Edge[] MST = new Edge[V - 1];
int mstIndex = 0;
int mstWeight = 0;
for (int i = 0; i E; i++) {
if (mstIndex == V - 1) break;
Edge edge = edges[i];
int srcParent = findParent(parent, edge.src);
int destParent = findParent(parent, edge.dest);
if (srcParent != destParent) {
MST[mstIndex++] = edge;
mstWeight += edge.weight;
union(parent, rank, srcParent, destParent);
}
}
System.out.println(Edges in the MST);
System.out.println(SrctDesttWeight);
for (int i = 0; i mstIndex; i++) {
System.out.println(MST[i].src + -- + MST[i].dest + == +
MST[i].weight);
}
System.out.println(Total weight of MST + mstWeight);
}
}
public class MinSpanTree {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println(Enter number of vertices );
int V = sc.nextInt();
System.out.println(Enter number of edges );
int E = sc.nextInt();
KruskalAlgorithm graph = new KruskalAlgorithm(V, E);
System.out.println(Enter edges in the format src dest weight);
for (int i = 0; i E; i++) {
int src = sc.nextInt();
int dest = sc.nextInt();
int weight = sc.nextInt();
graph.addEdge(src, dest, weight);
}
graph.KruskalsMST();
sc.close();
}
}
