Java Kruskal: cheapest connecting forest and disjoint-set checks

Last updated: 29 Sept 20264 min read

tutorial

Kruskal’s algorithm builds a minimum-weight spanning forest by considering undirected edges in increasing weight order and accepting edges that join different components.

Java 8+. This is a complete program using JDK classes.

Connect components without closing a cycle

A depot network needs a set of links that connects reachable depots at minimum total link cost. This is not a shortest route from one depot to another. A cheap connecting tree can contain a longer individual route than the shortest-path solution.

After sorting, disjoint-set membership decides whether a candidate edge closes a cycle. A successful union reduces the component count. Self-loops and edges within an already joined component are skipped; parallel links can be considered independently.

A disconnected input returns a forest and a remaining component count. The program does not label that result a spanning tree. Zero and negative edge costs are allowed because cycle avoidance still supplies the relevant constraint.

Working program

import java.util.Arrays;
import java.util.Comparator;
public class DepotLinkForest {
    static final class Edge {
        final int from,to,cost;
        Edge(int from,int to,int cost){this.from=from;this.to=to;this.cost=cost;}
    }
    static final class Result { final long cost; final int components;
        Result(long cost,int components){this.cost=cost;this.components=components;} }
    static int root(int[] parent,int vertex){
        while(parent[vertex]!=vertex){parent[vertex]=parent[parent[vertex]];vertex=parent[vertex];}
        return vertex;
    }
    static Result connect(int vertices,Edge[] input){
        if(vertices<0)throw new IllegalArgumentException("Negative vertices");
        for(Edge edge:input)if(edge.from<0||edge.to<0||edge.from>=vertices||edge.to>=vertices)throw new IllegalArgumentException("Invalid endpoint");
        Edge[] edges=input.clone();Arrays.sort(edges,Comparator.comparingInt(edge->edge.cost));
        int[] parent=new int[vertices],sizes=new int[vertices];
        for(int v=0;v<vertices;v++){parent[v]=v;sizes[v]=1;}
        long cost=0;int components=vertices;
        for(Edge edge:edges){
            int a=root(parent,edge.from),b=root(parent,edge.to);if(a==b)continue;
            if(sizes[a]<sizes[b]){int temporary=a;a=b;b=temporary;}
            parent[b]=a;sizes[a]+=sizes[b];cost=Math.addExact(cost,edge.cost);components--;
        }
        return new Result(cost,components);
    }
    public static void main(String[] args){
        Result result=connect(4,new Edge[]{new Edge(0,1,4),new Edge(1,2,2),new Edge(2,3,3),new Edge(0,3,10)});
        System.out.println("cost="+result.cost+", components="+result.components);
        Result forest=connect(3,new Edge[]{new Edge(0,1,-2)});
        System.out.println("cost="+forest.cost+", components="+forest.components);
    }
}

Output

cost=9, components=1
cost=-2, components=2

Costs and boundaries

Sorting e edges uses O(e log e) work. Union by size and path halving add near-linear disjoint-set work across the edge scan. The copied edge array and component arrays occupy O(e+v) auxiliary storage. Checked long accumulation rejects a total that cannot be represented.

Common Mistakes

A disconnected forest is not one spanning tree.
Minimum total connection cost is not a shortest-path answer.
Do not forbid negative link costs just because Dijkstra forbids negative edge weights.