1. Introduction

Kruskal’s Algorithm is a greedy algorithm used to find the minimum spanning tree for a connected weighted graph. It works by sorting all the edges from the lowest weight to the highest, and then iteratively adding edges to the spanning tree, avoiding any cycle until the tree has V-1 edges (where V is the number of vertices).

2. Program Steps

1. Sort all the edges in ascending order of their weight.

2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If not, include it. Else, discard it.

3. Repeat step 2 until there are (V-1) edges in the spanning tree.

3. Code Program

class KruskalAlgorithm {
    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 edge[];

    KruskalAlgorithm(int v, int e) {
        V = v;
        E = e;
        edge = new Edge[E];
        for (int i = 0; i < e; ++i) {
            edge[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(edge);

        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 = edge[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("Following are the edges in the constructed MST");
        for (i = 0; i < e; ++i) {
            System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
        }
    }

    public static void main(String[] args) {
        int V = 4;
        int E = 5;
        KruskalAlgorithm ka = new KruskalAlgorithm(V, E);

        ka.edge[0].src = 0;
        ka.edge[0].dest = 1;
        ka.edge[0].weight = 10;

        ka.edge[1].src = 0;
        ka.edge[1].dest = 2;
        ka.edge[1].weight = 6;

        ka.edge[2].src = 0;
        ka.edge[2].dest = 3;
        ka.edge[2].weight = 5;

        ka.edge[3].src = 1;
        ka.edge[3].dest = 3;
        ka.edge[3].weight = 15;

        ka.edge[4].src = 2;
        ka.edge[4].dest = 3;
        ka.edge[4].weight = 4;

        ka.KruskalMST();
    }
}

Output:

Following are the edges in the constructed MST
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10