Kruskal's Algorithm - Java

Kruskal's Algorithm is a popular algorithm for finding the minimum spanning tree (MST) of a graph. An MST is a tree that spans all the vertices of a graph such that the sum of the weights of its edges is minimized. Kruskal's Algorithm can be used to find the MST of an undirected graph that may contain cycles, but the final output will be a tree (a connected, acyclic graph).

The algorithm works as follows:

Sort all the edges in the graph in non-decreasing order of their weights.
Start adding edges to the MST one by one, ignoring the edges that form a cycle in the current MST.
Continue step 2 until the number of edges in the MST is V-1, where V is the number of vertices in the graph.

Kruskal's Algorithm is a greedy algorithm, as it chooses the edges that minimize the total weight of the MST in each step. A union-find algorithm is used to keep track of the subsets in the MST and detect cycles.

Kruskal's Algorithm is suitable for sparse graphs and has a time complexity of O(E log E), where E is the number of edges in the graph.



import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Kruskal {
    static class Edge implements Comparable<Edge> {
        int source, destination, weight;

        public Edge(int source, int destination, int weight) {
            this.source = source;
            this.destination = destination;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge edge) {
            return this.weight - edge.weight;
        }
    }

    static class Subset {
        int parent, rank;
    }

    static int find(Subset subsets[], int i) {
        if (subsets[i].parent != i)
            subsets[i].parent = find(subsets, subsets[i].parent);

        return subsets[i].parent;
    }

    static 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++;
        }
    }

    static List<Edge> kruskal(List<Edge> edges, int V) {
        List<Edge> mst = new ArrayList<>();
        Collections.sort(edges);
        Subset subsets[] = new Subset[V];
        for (int v = 0; v < V; v++) {
            subsets[v] = new Subset();
            subsets[v].parent = v;
            subsets[v].rank = 0;
        }

        int e = 0;
        int i = 0;
        while (e < V - 1) {
            Edge edge = edges.get(i++);
            int x = find(subsets, edge.source);
            int y = find(subsets, edge.destination);

            if (x != y) {
                mst.add(edge);
                e++;
                union(subsets, x, y);
            }
        }
        return mst;
    }

    public static void main(String[] args) {
        int V = 4;
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 10));
        edges.add(new Edge(0, 2, 6));
        edges.add(new Edge(0, 3, 5));
        edges.add(new Edge(1, 3, 15));
        edges.add(new Edge(2, 3, 4));
        List<Edge> mst = kruskal(edges, V);
        for (Edge edge : mst) {
            System.out.println(edge.source + " - " + edge.destination +
                     " : " + edge.weight);
        }
    }
}

Explanation:

The Edge class represents a weighted edge in the graph. It has three fields: source, destination, and weight.
The Subset class represents a subset for a union-find algorithm. It has two fields: parent and rank.
The find function returns the representative/root of a subset, using path compression.
The union function performs union of two subsets. The smaller subset is merged into the larger subset.
The kruskal function sorts the edges by their weights, then repeatedly adds the next smallest edge to the minimum spanning tree (MST) if it does not form a cycle in the current MST. This is done using a union-find algorithm.
The main function adds a sample set of edges to the list of edges, then calls the kruskal function to get the MST.

Output: