This Java program demonstrates the implementation of Kruskal’s algorithm to find the minimum spanning tree of a weighted, undirected graph. Kruskal’s algorithm works by sorting all edges in the graph in ascending order by weight, then iteratively adding edges to the MST, ensuring that each new edge does not form a cycle.

Java Code

import java.util.*;

class Edge implements Comparable {
    int src, dest, weight;

    public int compareTo(Edge compareEdge) {
        return this.weight - compareEdge.weight;
    }
}

class Subset {
    int parent, rank;
}

class Graph {
    int vertices, edges;
    Edge edge[];

    Graph(int v, int e) {
        vertices = v;
        edges = e;
        edge = new Edge[edges];
        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[vertices];
        int e = 0;
        int i = 0;
        for (i = 0; i < vertices; ++i)
            result[i] = new Edge();

        Arrays.sort(edge);

        Subset subsets[] = new Subset[vertices];
        for (i = 0; i < vertices; ++i) {
            subsets[i] = new Subset();
            subsets[i].parent = i;
            subsets[i].rank = 0;
        }

        i = 0;
        while (e < vertices - 1) {
            Edge next_edge = new Edge();
            if (i < edges) {
                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);
            }
        }

        for (i = 0; i < e; ++i)
            System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
    }
}

public class KruskalsAlgorithm {
    public static void main(String[] args) {
        int vertices = 4;
        int edges = 5;
        Graph graph = new Graph(vertices, edges);

        // add edge 0-1
        graph.edge[0].src = 0;
        graph.edge[0].dest = 1;
        graph.edge[0].weight = 10;

        // add edge 0-2
        graph.edge[1].src = 0;
        graph.edge[1].dest = 2;
        graph.edge[1].weight = 6;

        // add edge 0-3
        graph.edge[2].src = 0;
        graph.edge[2].dest = 3;
        graph.edge[2].weight = 5;

        // add edge 1-3
        graph.edge[3].src = 1;
        graph.edge[3].dest = 3;
        graph.edge[3].weight = 15;

        // add edge 2-3
        graph.edge[4].src = 2;
        graph.edge[4].dest = 3;
        graph.edge[4].weight = 4;

        graph.KruskalMST();
    }
}

Explanation of the Code

The program defines several classes to handle the graph and its edges. Here’s a breakdown of each class:

• Edge: Represents a graph edge with source, destination, and weight. It implements Comparable for sorting.
• Subset: Represents a subset for the union-find algorithm to detect cycles.
• Graph: Represents the whole graph. It includes methods to find the root of the subset (with path compression), union two subsets, and compute the MST using Kruskal’s algorithm.

The KruskalMST method sorts all the edges, then iteratively adds them to the MST, ensuring no cycles are formed using the union-find algorithm. It prints the resulting MST edges with their weights, demonstrating the edges selected for the MST.