Offensive Security Researcher & Quantum Cryptography Analyst

Kruskal’s Algorithm: Working, Explanation, and Minimum Spanning Tree Construction

Abdul Wahab Junaid
kruskal's algorithm and working of this algorithm

kruskal's algorithm and working of this algorithm

Whenever I’ve needed to connect a set of points — cities, computers, circuit components — using the least total amount of “wire,” I’ve turned to Kruskal’s algorithm. It solves the minimum spanning tree problem: given a connected, weighted, undirected graph, it finds a subset of edges that connects all vertices together, without any cycles, at the minimum possible total edge weight. What I find particularly satisfying about Kruskal’s approach is how directly it embraces greediness — sort all the edges by weight, and just keep adding the cheapest one that doesn’t create a cycle — and yet this simple strategy is provably optimal.

History and Background

I credit this algorithm to Joseph Kruskal, who published it in 1956 in a paper titled “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem.” Interestingly, the underlying idea of building a minimum spanning tree by always selecting the globally cheapest available edge had actually been described even earlier by Otakar BorĹŻvka in 1926, in the context of designing an efficient electrical network in Moravia, making it one of the oldest graph algorithms in existence, predating modern computing entirely. Kruskal’s specific formulation, however, is the one most commonly taught today, largely because of how naturally it pairs with the Union-Find (Disjoint Set) data structure for efficient cycle detection.

Problem Statement

I’m given a connected, undirected graph with weighted edges, and I want to find a spanning tree — a subset of edges that connects all vertices without forming any cycle — whose total edge weight is as small as possible. If the graph has n vertices, any spanning tree must have exactly n - 1 edges. There may be multiple minimum spanning trees if some edge weights are equal, but the total minimum weight itself is always unique. Kruskal’s algorithm solves this by greedily selecting edges in increasing order of weight, using a mechanism to avoid ever forming a cycle.

Core Concepts

How It Works

I proceed as follows:

  1. I sort all edges of the graph in non-decreasing order of weight.
  2. I initialize a Union-Find structure where every vertex starts in its own separate set.
  3. I process edges one at a time, in sorted order. For each edge (u, v, w), I check whether u and v are already in the same set (using the Union-Find’s “find” operation).
  4. If they are in different sets, adding this edge cannot create a cycle, so I include it in the MST and merge (union) the two sets.
  5. If they are already in the same set, adding this edge would create a cycle, so I skip it.
  6. I continue until I’ve included exactly n - 1 edges (or I’ve processed all edges, whichever comes first).

Working Principle

The algorithm’s correctness rests on the cut property of minimum spanning trees. At every step, when I consider the next cheapest unprocessed edge, if it connects two vertices currently in different components (sets), then this edge is guaranteed to be the minimum-weight edge crossing the cut between those two components (since I always process edges in increasing weight order, and any earlier, cheaper edge crossing that same cut would already have been considered and either included or would have connected the same two components already). The cut property guarantees this edge belongs to some MST, so including it is always a safe, correct greedy choice. Conversely, when an edge would connect two vertices already in the same component, including it would necessarily form a cycle, and by the cycle property, it cannot be part of any minimum spanning tree (since it would be the maximum weight edge in the cycle it creates, given the sorted processing order).

Mathematical Foundation

Formally, let G = (V, E) be a connected, weighted graph. The Minimum Spanning Tree T is the spanning tree minimizing:

$$ \text{weight}(T) = \sum_{(u,v) \in T} w(u,v) $$

among all possible spanning trees of G.

Cut Property (formal statement): For any cut (S, V \setminus S) of the graph’s vertices into two non-empty disjoint sets, if e is the minimum-weight edge with one endpoint in S and the other in V \setminus S, then there exists a minimum spanning tree containing e.

The total time complexity of Kruskal’s algorithm is dominated by sorting the edges, which takes O(|E| \log |E|), combined with O(|E| \alpha(|V|)) for the Union-Find operations, where α is the inverse Ackermann function (effectively a very small constant for all practical input sizes):

$$ T(|V|, |E|) = O(|E| \log |E|) $$

which is equivalent to O(|E| \log |V|) since |E| is at most O(|V|^2).

Diagrams

flowchart TD
    A[Sort all edges by weight in increasing order] --> B[Initialize Union-Find: each vertex its own set]
    B --> C[MST = empty set]
    C --> D{More edges remaining and MST has fewer than n-1 edges?}
    D -- No --> H[Return MST]
    D -- Yes --> E[Take next cheapest edge u-v-w]
    E --> F{find u == find v?}
    F -- Yes: same set, cycle --> D
    F -- No: different sets --> G[Add edge to MST; union u and v]
    G --> D

Pseudocode

function kruskal(graph, V):
    MST = []
    edges = all edges of graph, sorted by weight ascending

    // Union-Find initialization
    parent[i] = i for each vertex i
    rank[i] = 0 for each vertex i

    for each edge (u, v, w) in edges:
        if find(parent, u) != find(parent, v):
            MST.append((u, v, w))
            union(parent, rank, u, v)
        if length(MST) == V - 1:
            break

    return MST

function find(parent, i):
    if parent[i] != i:
        parent[i] = find(parent, parent[i])   // path compression
    return parent[i]

function union(parent, rank, x, y):
    rootX = find(parent, x)
    rootY = find(parent, y)
    if rootX == rootY:
        return
    if rank[rootX] < rank[rootY]:
        parent[rootX] = rootY
    elif rank[rootX] > rank[rootY]:
        parent[rootY] = rootX
    else:
        parent[rootY] = rootX
        rank[rootX] += 1

Step-by-Step Example

Consider a graph with vertices A, B, C, D and edges: A-B (1), A-C (3), B-C (3), B-D (6), C-D (4).

Sorted edges by weight: A-B(1), A-C(3), B-C(3), C-D(4), B-D(6).

Processing:

EdgeWeightSame set?ActionMST so far
A-B1NoAdd{A-B}
A-C3NoAdd{A-B, A-C}
B-C3Yes (both connect to A already)Skip (would form cycle){A-B, A-C}
C-D4NoAdd{A-B, A-C, C-D}
B-D6Yes (all connected now)Skip{A-B, A-C, C-D}

I stop once I have n - 1 = 3 edges. Final MST: A-B (1), A-C (3), C-D (4), with total weight 8.

Time Complexity

Space Complexity

Kruskal’s algorithm requires O(|E|) space to store and sort the edge list, plus O(|V|) space for the Union-Find parent and rank arrays. The resulting MST itself takes O(|V|) space, since it always contains exactly |V| - 1 edges.

Correctness Analysis

I prove correctness using the cut property, formalized earlier. I show, by induction on the number of edges added, that the set of edges chosen by Kruskal’s algorithm at any point is always a subset of some minimum spanning tree. The base case (no edges chosen) is trivially true. For the inductive step, when Kruskal’s algorithm adds an edge e = (u, v) because u and v are in different components, I can construct a cut where S is the component containing u and V \setminus S is everything else. Since all edges considered before e (by sorted order) either connected vertices already in the same component or were skipped for other reasons, e must be the minimum-weight edge crossing this cut among all edges not yet processed with a smaller or equal weight; more precisely, no smaller-weight edge could have connected these two specific components without already having been added. By the cut property, some MST contains an edge crossing this cut with weight at most w(e), and since Kruskal processes edges in increasing order, e is a valid minimal choice, so the invariant holds after adding e. By induction, the final set of |V|-1 edges chosen forms a valid minimum spanning tree.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int u, v, weight;
} Edge;

int parent[100], rankArr[100];

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

void unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX == rootY) return;

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

int compareEdges(const void *a, const void *b) {
    return ((Edge *)a)->weight - ((Edge *)b)->weight;
}

void kruskal(Edge edges[], int numEdges, int numVertices) {
    qsort(edges, numEdges, sizeof(Edge), compareEdges);

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

    int mstWeight = 0;
    int edgeCount = 0;

    printf("Edges in the Minimum Spanning Tree:\n");
    for (int i = 0; i < numEdges && edgeCount < numVertices - 1; i++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].weight;

        if (find(u) != find(v)) {
            unionSets(u, v);
            printf("%d - %d : %d\n", u, v, w);
            mstWeight += w;
            edgeCount++;
        }
    }

    printf("Total weight of MST: %d\n", mstWeight);
}

int main() {
    /* 0=A, 1=B, 2=C, 3=D */
    Edge edges[] = {
        {0, 1, 1}, /* A-B */
        {0, 2, 3}, /* A-C */
        {1, 2, 3}, /* B-C */
        {1, 3, 6}, /* B-D */
        {2, 3, 4}  /* C-D */
    };
    int numEdges = 5;
    int numVertices = 4;

    kruskal(edges, numEdges, numVertices);
    return 0;
}

Sample Input and Output

Input: graph with vertices A(0), B(1), C(2), D(3) and edges A-B(1), A-C(3), B-C(3), B-D(6), C-D(4).

Output:

Edges in the Minimum Spanning Tree:
0 - 1 : 1
0 - 2 : 3
2 - 3 : 4
Total weight of MST: 8

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version