Kruskal's Minimum Spanning Tree Algorithm: Notes, Example, Code & Complexity

Kruskal's Minimum Spanning Tree Algorithm

Kruskal's algorithm is a greedy algorithm for finding a Minimum Spanning Tree (MST) of a connected, undirected, weighted graph.

It sorts all edges by weight and adds the cheapest safe edge one by one.

Union-Find, also called Disjoint Set Union (DSU), is used to avoid cycles efficiently.

What is Kruskal's Minimum Spanning Tree Algorithm?

Kruskal's algorithm finds a minimum spanning tree of a weighted, undirected graph. A minimum spanning tree connects all vertices with the minimum possible total edge weight and contains no cycle.

The algorithm is greedy because it repeatedly picks the smallest available edge. However, it does not blindly add every small edge. It adds an edge only when that edge connects two different components and does not form a cycle.

Input: A connected, undirected graph with weighted edges.
Output: A set of V-1 edges forming the minimum spanning tree.
Main idea: Sort edges by weight, then keep the safe edges.
Cycle check: Use Union-Find to test whether two vertices are already connected.

Where Kruskal's Algorithm Is Used

Kruskal is useful whenever we want to connect multiple points with the minimum total cost.

Network design: connect routers, towers, or offices with minimum cable cost.
Road or railway planning: connect cities while minimizing construction cost.
Clustering: MST edges can be cut to form groups.
Exam and interview problems: MST is a classic greedy algorithm topic in DAA.

Important Terms Before the Algorithm

Term	Meaning
Spanning Tree	A tree that connects all vertices of a connected graph without cycles
Minimum Spanning Tree	A spanning tree with the minimum possible total edge weight
Component	A connected group of vertices formed so far
Safe Edge	An edge that can be added without creating a cycle
Union-Find	A data structure used to check and merge connected components

Kruskal Algorithm Steps

The algorithm starts with no selected edges. Every vertex is treated as a separate component. Then edges are processed from smallest weight to largest weight.

Step 1: Sort all edges in ascending order of weight.
Step 2: Create an empty MST result.
Step 3: Put every vertex in its own disjoint set.
Step 4: Pick the next smallest edge.
Step 5: If the edge connects two different sets, add it to the MST and merge the sets.
Step 6: If the edge connects vertices already in the same set, skip it because it creates a cycle.
Step 7: Stop when the MST has V-1 edges.

Why Kruskal's Algorithm Works

Kruskal's algorithm is based on the cut property of MSTs. If we divide the graph into two parts, the lightest edge crossing that cut is safe to include in some minimum spanning tree.

When Kruskal picks the smallest edge that joins two different components, that edge is the cheapest way to connect those two separated parts at that moment. Since it does not create a cycle, it preserves the tree structure.

It always chooses the cheapest available safe edge.
It never adds an edge that creates a cycle.
It gradually merges components until all vertices are connected.
Because every chosen edge is safe, the final tree has minimum total weight.

Step-by-Step Example

Consider the following weighted undirected graph with 4 vertices: A, B, C, and D.

Edge	Weight
A - B	10
A - C	6
A - D	5
B - D	15
C - D	4

Dry Run of Kruskal's Algorithm

First sort the edges by weight: C-D(4), A-D(5), A-C(6), A-B(10), B-D(15).

Step	Edge Checked	Decision	Reason	MST Edges So Far
1	C - D (4)	Add	C and D are in different components	C-D
2	A - D (5)	Add	A is separate, D is in component C-D	C-D, A-D
3	A - C (6)	Skip	A and C are already connected through D, so this forms a cycle	C-D, A-D
4	A - B (10)	Add	B is separate, so this connects a new vertex	C-D, A-D, A-B

Final MST Result

The graph has 4 vertices, so the MST must contain V-1 = 3 edges. After selecting 3 edges, the algorithm stops.

Selected edges: C-D, A-D, A-B.
Total MST weight: 4 + 5 + 10 = 19.
Skipped edge A-C because it creates a cycle.
Skipped edge B-D because the MST is already complete.

Union-Find Role in Kruskal's Algorithm

The most important implementation detail in Kruskal's algorithm is cycle detection. If we check cycles by traversing the graph every time, the algorithm becomes slow. Union-Find solves this problem efficiently.

find(x): returns the representative parent of vertex x.
union(x, y): merges the components of x and y.
If find(u) == find(v), u and v are already connected, so edge u-v creates a cycle.
If find(u) != find(v), the edge is safe and both components can be merged.
Path compression and union by rank make Union-Find very fast in practice.

Java Program for Kruskal's Algorithm

The following program stores each edge as {u, v, weight}, sorts edges by weight, and uses Union-Find to build the MST.

Kruskal Minimum Spanning Tree in Java

import java.util.*;

public class KruskalMST {

    static class Edge {
        int u, v, weight;

        Edge(int u, int v, int weight) {
            this.u = u;
            this.v = v;
            this.weight = weight;
        }
    }

    static class DSU {
        int[] parent;
        int[] rank;

        DSU(int n) {
            parent = new int[n];
            rank = new int[n];

            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

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

        boolean union(int a, int b) {
            int rootA = find(a);
            int rootB = find(b);

            if (rootA == rootB) {
                return false; // cycle would be formed
            }

            if (rank[rootA] < rank[rootB]) {
                parent[rootA] = rootB;
            } else if (rank[rootA] > rank[rootB]) {
                parent[rootB] = rootA;
            } else {
                parent[rootB] = rootA;
                rank[rootA]++;
            }

            return true;
        }
    }

    static int kruskal(int vertices, List<Edge> edges) {
        edges.sort(Comparator.comparingInt(edge -> edge.weight));

        DSU dsu = new DSU(vertices);
        int totalWeight = 0;
        int selectedEdges = 0;

        System.out.println("Edges in MST:");

        for (Edge edge : edges) {
            if (dsu.union(edge.u, edge.v)) {
                System.out.println(edge.u + " - " + edge.v + " : " + edge.weight);
                totalWeight += edge.weight;
                selectedEdges++;

                if (selectedEdges == vertices - 1) {
                    break;
                }
            }
        }

        return totalWeight;
    }

    public static void main(String[] args) {
        int vertices = 4;
        List<Edge> edges = new ArrayList<>();

        edges.add(new Edge(0, 1, 10)); // A-B
        edges.add(new Edge(0, 2, 6));  // A-C
        edges.add(new Edge(0, 3, 5));  // A-D
        edges.add(new Edge(1, 3, 15)); // B-D
        edges.add(new Edge(2, 3, 4));  // C-D

        int mstWeight = kruskal(vertices, edges);
        System.out.println("Total MST Weight = " + mstWeight);
    }
}

Program Output

Output

Edges in MST:
2 - 3 : 4
0 - 3 : 5
0 - 1 : 10
Total MST Weight = 19

Time and Space Complexity

Let V be the number of vertices and E be the number of edges.

Operation	Complexity	Explanation
Sorting edges	O(E log E)	All edges are sorted by weight
Union-Find operations	Almost O(E)	With path compression and union by rank
Overall time	O(E log E)	Sorting dominates the running time
Space complexity	O(V + E)	Edges plus parent and rank arrays

Kruskal vs Prim

Point	Kruskal	Prim
Approach	Edge-based	Vertex/tree-based
Main operation	Sort all edges and pick safe edges	Grow one tree by cheapest outgoing edge
Data structure	Union-Find	Priority queue
Best for	Sparse graphs	Dense graphs

Common Mistakes

Using Kruskal on a directed graph. Classical MST is for undirected graphs.
Adding the smallest edge without checking for cycles.
Stopping after V edges instead of V-1 edges.
Forgetting to sort edges by weight.
Confusing MST with shortest path. MST minimizes total tree cost, not distance from a source.
Not handling disconnected graphs. In a disconnected graph, Kruskal creates a minimum spanning forest, not one MST.

Key Takeaways

Kruskal's algorithm is a greedy MST algorithm.
It sorts edges by weight and selects the cheapest safe edges.
Union-Find helps detect cycles efficiently.
The MST contains exactly V-1 edges.
The usual time complexity is O(E log E).
Kruskal is especially suitable for sparse graphs.

Key Takeaways

Can you explain why sorting edges is necessary?
Can you dry-run Kruskal on a small weighted graph?
Can you identify when an edge should be skipped?
Can you explain the role of Union-Find?
Can you calculate the final MST weight?

Common Mistakes to Avoid

WRONG Add every edge after sorting by weight.

RIGHT Add an edge only if its endpoints are in different components.

In Kruskal, the cycle check is mandatory. If find(u) == find(v), skip the edge.

WRONG Stop after selecting V edges.

RIGHT Stop after selecting V - 1 edges.

A spanning tree with V vertices always has exactly V - 1 edges.

WRONG Use Kruskal to find shortest paths from a source vertex.

RIGHT Use Kruskal to build a minimum spanning tree.

Shortest path algorithms minimize distance from a source. MST algorithms minimize total connection cost.

Practice Tasks

Draw a graph with 5 vertices and 7 weighted edges, then find its MST using Kruskal.
Modify the Java program to print vertex names A, B, C instead of numbers.
Try a graph with equal edge weights and observe that more than one MST may be possible.
Test a disconnected graph and identify the minimum spanning forest.

Frequently Asked Questions

Is Kruskal's algorithm greedy?

Yes. It makes a greedy choice by selecting the smallest safe edge at each step.

Why do we need Union-Find in Kruskal?

Union-Find quickly tells whether two vertices are already connected. If they are connected, adding the edge would create a cycle.

Can Kruskal handle negative edge weights?

Yes. Negative weights are allowed in MST problems. The edges are still sorted by weight, and the same cycle-checking rule applies.

How many edges are present in the final MST?

For a connected graph with V vertices, the MST has exactly V-1 edges.

What happens if the graph is disconnected?

A single MST cannot be formed. Kruskal will produce a minimum spanning forest, one tree for each connected component.

Previous Next

Kruskal's Minimum Spanning Tree Algorithm: Notes, Example, Code & Complexity