How to Implement the Kruskal’s Algorithm -

laptop infographic online business 6087062

Introduction

Kruskal’s Algorithm is a greedy algorithm. It is used for determining the Minimum Spanning Tree (MST) of a connected, and undirected graph. It connects all vertices using the smallest total edge weight possible, while ensuring that no cycles are created.

How Kruskal’s Algorithm Works

Kruskal’s Algorithm constructs the Minimum Spanning Tree by following these key steps:

The process continues until the MST includes exactly V - 1 edges, where V is the total number of vertices in the graph.
Begin by sorting all the edges in ascending order based on their weights.
Create an empty set to store the edges of the MST.
Go through the sorted edges one at a time, and include each edge in the MST only if it doesn’t create a cycle with the edges already selected.
To efficiently check for cycles, use a Union-Find (Disjoint Set Union) data structure.
The process continues until the MST includes exactly V - 1 edges, where V is the total number of vertices in the graph.

Union-Find Structure

The Union-Find data structure helps track connected components and ensures that adding an edge doesn’t create a cycle. It supports two main operations:

Find: Determines the root of a node.
Union: Merges two subsets.

Java Implementation

Here is a complete Java example demonstrating Kruskal’s Algorithm:

public class KruskalAlg {
    public static void main(String[] args) {
        int graphVertices = 6;
        List<GraphEdge> graphEdges = new ArrayList<>();

        graphEdges.add(new KruskalAlg().new GraphEdge(0, 1, 4));
        graphEdges.add(new KruskalAlg().new GraphEdge(0, 2, 4));
        graphEdges.add(new KruskalAlg().new GraphEdge(1, 2, 2));
        graphEdges.add(new KruskalAlg().new GraphEdge(1, 3, 5));
        graphEdges.add(new KruskalAlg().new GraphEdge(2, 3, 5));
        graphEdges.add(new KruskalAlg().new GraphEdge(2, 4, 11));
        graphEdges.add(new KruskalAlg().new GraphEdge(3, 4, 2));
        graphEdges.add(new KruskalAlg().new GraphEdge(3, 5, 1));
        graphEdges.add(new KruskalAlg().new GraphEdge(4, 5, 7));

        List<GraphEdge> mst = kruskalMST(graphVertices, graphEdges);

        System.out.println("Edges in the Minimum Spanning Tree:");
        for (GraphEdge e : mst) {
            System.out.println(e.src + " - " + e.dest + " : " + e.weight);
        }
    }

    static List<GraphEdge> kruskalMST(int vertices, List<GraphEdge> edges) {
        Collections.sort(edges);
        UnionFindOp uf = new KruskalAlg().new UnionFindOp(vertices);
        List<GraphEdge> mst = new ArrayList<>();

        for (GraphEdge edge : edges) {
            if (uf.union(edge.src, edge.dest)) {
                mst.add(edge);
                if (mst.size() == vertices - 1)
                    break;
            }
        }

        return mst;
    }
    
    class GraphEdge implements Comparable<GraphEdge> {
        int src, dest, weight;

        GraphEdge(int s, int d, int w) {
            this.src = s;
            this.dest = d;
            this.weight = w;
        }

        public int compareTo(GraphEdge other) {
            return this.weight - other.weight;
        }
    }

    class UnionFindOp {
        int[] parent, rank;

        UnionFindOp(int size) {
            parent = new int[size];
            rank = new int[size];
            for (int i = 0; i < size; i++)
                parent[i] = i;
        }

        int find(int x) {
            if (parent[x] != x)
                parent[x] = find(parent[x]);
            return parent[x];
        }

        boolean union(int x, int y) {
            int xr = find(x);
            int yr = find(y);
            if (xr == yr) return false;

            if (rank[xr] < rank[yr]) {
                parent[xr] = yr;
            } else if (rank[xr] > rank[yr]) {
                parent[yr] = xr;
            } else {
                parent[yr] = xr;
                rank[xr]++;
            }
            return true;
        }
    }
}

Output

yamlCopiaModificaEdges in the Minimum Spanning Tree:
3 - 5 : 1
1 - 2 : 2
3 - 4 : 2
0 - 1 : 4
4 - 5 : 7

Note: Output may vary depending on the order of edge processing if multiple MSTs are valid.

Time Complexity

The time complexity is primarily dictated by the sorting step and the Union-Find operations:

Sorting edges: O(E log E)
Union-Find operations: O(E α(V)) with path compression (where α is the inverse Ackermann function, very slow-growing)

Hence, the overall complexity is O(E log E), which is efficient for sparse graphs.

Conclusion

Kruskal’s Algorithm is an intuitive and efficient method for constructing a Minimum Spanning Tree, especially useful for sparse graphs. With the support of a Union-Find structure, it prevents cycles and ensures optimality. The Java implementation above offers a practical way to apply this algorithm in real-world graph problems.

You can find the example code on Github.