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.