# 1. Introduction

The Minimum Spanning Tree (MST) of a graph represents a tree with the minimum possible sum of edge weights that connects all vertices. Kruskal’s algorithm is a popular method to find the MST of a connected graph. It is a greedy algorithm that sorts all the edges in increasing order by weight, and then selects edges one by one, ensuring no cycle is formed.

# 2. Program Steps

1. Define structures to represent a graph and a disjoint set.

2. Sort all edges in increasing order of weight.

3. Iterate through the sorted edges.

4. For every edge, check if it forms a cycle with the spanning tree formed so far using disjoint sets. If no cycle is formed, include this edge; otherwise, discard it.

5. Continue the process until the spanning tree has *V-1* edges (where *V* is the number of vertices).

# 3. Code Program

```
// Class to represent a graph
class Graph {
// Nested class to represent an edge
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 v, int e) {
V = v;
E = e;
edges = new Edge[E];
for (int i = 0; i < e; 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 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++;
}
}
void KruskalMST() {
Edge[] result = new Edge[V];
int e = 0;
int i = 0;
for (i = 0; i < V; i++)
result[i] = new Edge();
Arrays.sort(edges);
Subset[] subsets = new Subset[V];
for (i = 0; i < V; i++)
subsets[i] = new Subset();
for (int v = 0; v < V; v++) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
i = 0;
while (e < V - 1) {
Edge next_edge = edges[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
if (x != y) {
result[e++] = next_edge;
union(subsets, x, y);
}
}
System.out.println("Edges in the constructed MST:");
for (i = 0; i < e; i++)
System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
}
}
public class Main {
public static void main(String[] args) {
int V = 4; // Number of vertices
int E = 5; // Number of edges
Graph graph = new Graph(V, E);
graph.edges[0].src = 0;
graph.edges[0].dest = 1;
graph.edges[0].weight = 10;
graph.edges[1].src = 0;
graph.edges[1].dest = 2;
graph.edges[1].weight = 6;
graph.edges[2].src = 0;
graph.edges[2].dest = 3;
graph.edges[2].weight = 5;
graph.edges[3].src = 1;
graph.edges[3].dest = 3;
graph.edges[3].weight = 15;
graph.edges[4].src = 2;
graph.edges[4].dest = 3;
graph.edges[4].weight = 4;
graph.KruskalMST();
}
}
```

### Output:

Edges in the constructed MST: 2 -- 3 == 4 0 -- 3 == 5 0 -- 1 == 10

# 4. Step By Step Explanation

1. We begin by defining the structure of our *Graph* class with nested classes for *Edge* and *Subset*.

2. The *Edge* class contains *src*, *dest*, and *weight*. It also implements *Comparable* to help sort the edges based on their weight.

3. *Subset* is used to represent a disjoint set. It contains *parent* and *rank* attributes.

4. The *find* method helps in finding the set of an element *i* using path compression technique.

5. The *union* method unites two sets of *x* and *y* with the use of union-by-rank.

6. Inside the *KruskalMST* method, we start by sorting all the edges in ascending order of weight using *Arrays.sort()*.

7. The sorted edges are iteratively processed. For each edge, we check if adding it to the result causes a cycle. If not, it is included in the result.

8. Finally, the constructed MST is printed out.

9. The *Main* class demonstrates the Kruskal's algorithm on a sample graph.