Implementing Kruskal's Algorithm in Java

Good evening, Hashnode Community! 🌍

Today, I dissect an extract of Java code that implements the Kruskal algorithm for finding the minimum spanning tree in a connected, undirected graph.

Start by understanding some key components:

1. DisjointSet:

This is an auxiliary data structure from the Kruskal algorithm to manage collections of disjoint sets.

Find: Determines which set a particular element belongs to. It returns a representative member of the set.
Union: Merges two different sets into a single Set.

2. Kruskal:

This class contains methods that implement the Kruskal algorithm.

worst_case: This method demonstrates how to utilize the algorithm using a predefined set of edges.
Kruskal: This method provides the Kruskal algorithm logic.

How does the Kruskal Algorithm Work:

Initialization: Start with a forest of disjoint single-node trees, one for each vertex.
Sorting: Sort the edges by weight in non-decreasing order.
Edge Addition: For every edge, in non-decreasing order, if the edge connects two different trees, add it to the forest, merging two trees into a single tree. If the edge connects nodes from the same tree, skip it (to avoid a cycle).
Termination: The algorithm finishes once we've added (V-1) edges where V is the number of vertices.

Code Extract

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class DisjointSet {
    private int[] parent;
    private int[] rank;

    public DisjointSet(int n) {
        parent = new int[n + 1]; // To account for 1-indexed nodes
        rank = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }

    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) {
            return false; // Already in the same set
        }

        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }

        return true;
    }
}

public class Kruskal {

    int[][] example_1 = new int[][] { { 0, 1, 3, Integer.MAX_VALUE, Integer.MAX_VALUE },
            { 1, 0, 3, 6, Integer.MAX_VALUE },
            { 3, 3, 0, 4, 2 },
            { Integer.MAX_VALUE, 6, 4, 0, 5 },
            { Integer.MAX_VALUE, Integer.MAX_VALUE, 2, 5, 0 } };

    public void worst_case() {

        int n = 5;
        int m = 7;

        Set<Edge> E = new HashSet<>();

        E.add(new Edge(1, 2, 1));
        E.add(new Edge(1, 3, 3));
        E.add(new Edge(2, 3, 3));
        E.add(new Edge(2, 4, 6));
        E.add(new Edge(3, 4, 4));
        E.add(new Edge(3, 5, 2));
        E.add(new Edge(4, 5, 5));

        // Convert the Set to a List
        List<Edge> edgeList = new ArrayList<>(E);

        // Sorting the List
        edgeList.sort(Comparator.comparingInt(Edge::getWeight));

        // Printing the sorted edges
        // for (Edge edge : edgeList) {
        // System.out.println("From: " + edge.getU() + " To: " + edge.getV() + " Weight:
        // " + edge.getWeight());
        // }

        // create a disjoint set.
        DisjointSet disjointSet = new DisjointSet(n);

        // create a list to store the MST edges
        List<Edge> mst = new ArrayList<>();

        // iterate through all the edges in the sorted order
        for (Edge edge : edgeList) {
            // if the edge is not forming a cycle, add it to the MST
            if (disjointSet.union(edge.getU(), edge.getV())) {
                mst.add(edge);
            }
        }

        // display the edges in the MST
        System.out.println("Minimum Spanning Tree: ");

        for (Edge edge : mst) {
            System.out.println("From: " + edge.getU() + " To: " + edge.getV() + " Weight: " + edge.getWeight());
        }

    }

    public Set<Edge> kruskal(int n, int m, Set<Edge> E) {
        int i, j;

        Set<Edge> P = new HashSet<>();
        Set<Edge> Q = new HashSet<>();

        Edge e = new Edge(0, 0, 0);

        Set<Edge> F = new HashSet<>();

        while (F.size() < (n - 1)) {

            for (i = 0; i < m; i++) {
                e = E.iterator().next();
                E.remove(e);
                P.add(e);
            }

            for (i = 0; i < m; i++) {
                e = P.iterator().next();
                P.remove(e);
                if (e.getU() != e.getV()) {
                    F.add(e);
                    break;
                } else {
                    Q.add(e);
                }
            }

            for (i = 0; i < m; i++) {
                e = Q.iterator().next();
                Q.remove(e);
                P.add(e);
            }

        }

        return F;

    }
}

Deep Dive into the Code:

Within the Kruskal Class:

worst_case: This method first initializes a set of edges. It then sorts these edges based on their weights. The code then goes through these edges and adds them to the minimum spanning tree if they do not form a cycle.
Kruskal: This method seems a bit more complicated, with multiple for loops and sets P, Q, and F.

However, the provided Kruskal method does not follow the traditional Kruskal algorithm. Instead, it showcases an alternate approach to building the minimum spanning tree by repetitively iterating through edges.

Recommendations:

Comments: Developers pepper their code with documentation, especially when implementing complex algorithms. This helps others understand your code but can also be a boon for future you.
Edge Class: The Edge class is not provided in the shared code because it is imported from another file.

Conclusion:

The Kruskal algorithm is a crucial tool in graph theory and network design. With object-oriented capabilities and a rich standard library, implementing such algorithms becomes streamlined.

Feel free to tweak, optimize, or repurpose the code to suit your needs. Remember, programming is as much about understanding and iterating as it is about typing the initial lines of code.

Happy Coding! 💻🚀

[Coding Tutorials 2] Understanding Kruskal's Algorithm Through Java

Table of contents