ProgramGuru

Kruskal's Algorithm - Minimum Spanning Tree

Problem and examples

Given a connected, undirected, weighted graph with V vertices and E edges, the goal is to compute the sum of the edge weights of the Minimum Spanning Tree (MST). The MST is a subset of the edges that connects all vertices together, without any cycles, and with the minimum total edge weight.

Vertices (V) Edges MST Weight Description
4 [(0,1,1), (0,2,3), (1,2,1), (1,3,4), (2,3,2)] 4 Edges chosen: (0-1), (1-2), (2-3)
3 [(0,1,10), (1,2,5), (0,2,15)] 15 Edges chosen: (1-2), (0-1)
5 [(0,1,1), (0,2,7), (1,2,5), (1,3,4), (2,4,6), (3,4,2)] 12 MST edges avoid cycles and select minimal weights
1 [] 0 Single node, no edges
2 [(0,1,100)] 100 Only one edge to connect the two nodes

How it works

Understanding the Problem

We are given an undirected, weighted graph. Our goal is to find the Minimum Spanning Tree (MST) — a subset of the edges that connects all vertices with the minimum possible total edge weight, and without forming any cycles.

This means we want to connect all nodes together in the cheapest way possible, avoiding any loops. Among many possible algorithms, Kruskal’s Algorithm is one of the most popular and intuitive methods to solve this.

It works by sorting the edges by weight and picking the smallest ones first — only if they don't form a cycle. To efficiently detect cycles, we use a data structure called Disjoint Set Union (DSU) or Union-Find.

Step-by-Step Solution with Example

Step 1: Understand the Input

Let’s take an example graph:


Vertices: 4
Edges: 
(0 - 1, weight 10)
(0 - 2, weight 6)
(0 - 3, weight 5)
(1 - 3, weight 15)
(2 - 3, weight 4)

Step 2: Sort All Edges by Weight

We sort all edges in non-decreasing order of their weight:


(2 - 3, weight 4)
(0 - 3, weight 5)
(0 - 2, weight 6)
(0 - 1, weight 10)
(1 - 3, weight 15)

Step 3: Initialize Disjoint Sets

Each vertex starts as its own parent in the DSU. No vertices are connected initially. We'll connect them as we pick edges.

Step 4: Process Each Edge

We go through each edge in sorted order:

  • Edge (2 - 3): 2 and 3 are in different sets → include this edge in MST.
  • Edge (0 - 3): 0 and 3 are in different sets → include this edge in MST.
  • Edge (0 - 2): 0 and 2 are in different sets → include this edge in MST.
  • Edge (0 - 1): 0 and 1 are now in the same set → including this would form a cycle → skip.
  • Edge (1 - 3): 1 and 3 are already connected → skip to avoid cycle.

Step 5: Stop When MST Has V - 1 Edges

We stop when we have V - 1 = 3 edges in the MST (since we have 4 vertices).

Final MST Edges:


(2 - 3, weight 4)
(0 - 3, weight 5)
(0 - 2, weight 6)

Total Weight = 4 + 5 + 6 = 15

Edge Cases

  • Disconnected Graph: Kruskal’s Algorithm cannot form a complete MST if the graph is not connected. It will return a spanning forest instead.
  • Multiple Same-Weight Edges: The algorithm still works as long as DSU correctly avoids cycles.
  • Self-loops or Parallel Edges: Self-loops should be ignored. For parallel edges, the one with the smallest weight should be considered.
  • Already a Tree: If the input graph is already a tree, no edge will be skipped, and the result is the original graph itself.

Finally

Kruskal’s Algorithm is a greedy algorithm — it picks the best choice at each step by always selecting the smallest edge. Using the DSU efficiently ensures cycle detection is fast, making Kruskal’s a powerful algorithm for building MSTs — especially for sparse graphs.

By working step by step and thinking about edge selection intuitively, beginners can clearly see how Kruskal’s avoids cycles and builds the MST optimally.

  1. Sort all edges of the graph in increasing order of weight.
  2. Initialize a Disjoint Set data structure (Union-Find) for all vertices.
  3. Initialize mst_weight = 0.
  4. Iterate over sorted edges:
    1. For each edge (u, v, w), check if u and v belong to different sets.
    2. If they do, add the edge to the MST and union the sets.
    3. Add the weight w to mst_weight.
  5. Continue until MST includes exactly V - 1 edges.
  6. Return mst_weight as the final result.

Implementation and efficiency

C implementation

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

// Disjoint Set Union (Union-Find) implementation
typedef struct {
    int *parent;
    int *rank;
    int size;
} DisjointSet;

DisjointSet *createDisjointSet(int n) {
    DisjointSet *ds = (DisjointSet *)malloc(sizeof(DisjointSet));
    ds->parent = (int *)malloc(n * sizeof(int));
    ds->rank = (int *)calloc(n, sizeof(int));
    ds->size = n;
    for (int i = 0; i < n; i++) {
        ds->parent[i] = i;
    }
    return ds;
}

int findParent(DisjointSet *ds, int u) {
    if (ds->parent[u] != u) {
        ds->parent[u] = findParent(ds, ds->parent[u]);
    }
    return ds->parent[u];
}

int unionSets(DisjointSet *ds, int u, int v) {
    int pu = findParent(ds, u);
    int pv = findParent(ds, v);
    if (pu == pv) return 0;
    if (ds->rank[pu] < ds->rank[pv]) {
        ds->parent[pu] = pv;
    } else if (ds->rank[pu] > ds->rank[pv]) {
        ds->parent[pv] = pu;
    } else {
        ds->parent[pv] = pu;
        ds->rank[pu]++;
    }
    return 1;
}

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

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

int kruskalMST(int V, Edge edges[], int E) {
    qsort(edges, E, sizeof(Edge), compareEdges);
    DisjointSet *ds = createDisjointSet(V);
    int mstWeight = 0;
    int edgeCount = 0;

    for (int i = 0; i < E; i++) {
        if (unionSets(ds, edges[i].u, edges[i].v)) {
            mstWeight += edges[i].weight;
            edgeCount++;
            if (edgeCount == V - 1) break;
        }
    }
    free(ds->parent);
    free(ds->rank);
    free(ds);
    return mstWeight;
}

int main() {
    int V = 4;
    Edge edges[] = {
        {0, 1, 1},
        {0, 2, 3},
        {1, 2, 1},
        {1, 3, 4},
        {2, 3, 2}
    };
    int E = sizeof(edges) / sizeof(edges[0]);
    int result = kruskalMST(V, edges, E);
    printf("MST weight: %d\n", result); // Output: 4
    return 0;
}

C++ implementation

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class DisjointSet {
    vector<int> parent, rank;
public:
    DisjointSet(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    int find(int u) {
        if (parent[u] != u)
            parent[u] = find(parent[u]);
        return parent[u];
    }
    bool unionSets(int u, int v) {
        int pu = find(u), pv = find(v);
        if (pu == pv) return false;
        if (rank[pu] < rank[pv])
            parent[pu] = pv;
        else if (rank[pu] > rank[pv])
            parent[pv] = pu;
        else {
            parent[pv] = pu;
            rank[pu]++;
        }
        return true;
    }
};

int kruskalMST(int V, vector<tuple<int,int,int>>& edges) {
    sort(edges.begin(), edges.end(), [](auto &a, auto &b) {
        return get<2>(a) < get<2>(b);
    });
    DisjointSet dsu(V);
    int mstWeight = 0, edgeCount = 0;

    for (auto &[u, v, w] : edges) {
        if (dsu.unionSets(u, v)) {
            mstWeight += w;
            edgeCount++;
            if (edgeCount == V - 1) break;
        }
    }
    return mstWeight;
}

int main() {
    int V = 4;
    vector<tuple<int,int,int>> edges = {
        {0, 1, 1},
        {0, 2, 3},
        {1, 2, 1},
        {1, 3, 4},
        {2, 3, 2}
    };
    int result = kruskalMST(V, edges);
    cout << "MST weight: " << result << endl; // Output: 4
    return 0;
}

Python implementation

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]
    def union(self, u, v):
        pu, pv = self.find(u), self.find(v)
        if pu == pv:
            return False
        if self.rank[pu] < self.rank[pv]:
            self.parent[pu] = pv
        elif self.rank[pu] > self.rank[pv]:
            self.parent[pv] = pu
        else:
            self.parent[pv] = pu
            self.rank[pu] += 1
        return True

def kruskalMST(V, edges):
    edges.sort(key=lambda x: x[2])
    dsu = DisjointSet(V)
    mstWeight = 0
    edgeCount = 0
    for u, v, w in edges:
        if dsu.union(u, v):
            mstWeight += w
            edgeCount += 1
            if edgeCount == V - 1:
                break
    return mstWeight

edges = [
    (0, 1, 1),
    (0, 2, 3),
    (1, 2, 1),
    (1, 3, 4),
    (2, 3, 2)
]

print("MST weight:", kruskalMST(4, edges))  # Output: 4

Java implementation

import java.util.*;

class DisjointSet {
    private int[] parent, rank;

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

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

    public boolean union(int u, int v) {
        int pu = find(u);
        int pv = find(v);
        if (pu == pv) return false;
        if (rank[pu] < rank[pv]) {
            parent[pu] = pv;
        } else if (rank[pu] > rank[pv]) {
            parent[pv] = pu;
        } else {
            parent[pv] = pu;
            rank[pu]++;
        }
        return true;
    }
}

public class KruskalMST {
    public static int kruskalMST(int V, List<int[]> edges) {
        edges.sort(Comparator.comparingInt(a -> a[2]));
        DisjointSet dsu = new DisjointSet(V);
        int mstWeight = 0;
        int edgeCount = 0;

        for (int[] edge : edges) {
            if (dsu.union(edge[0], edge[1])) {
                mstWeight += edge[2];
                edgeCount++;
                if (edgeCount == V - 1) break;
            }
        }
        return mstWeight;
    }

    public static void main(String[] args) {
        int V = 4;
        List<int[]> edges = Arrays.asList(
            new int[]{0, 1, 1},
            new int[]{0, 2, 3},
            new int[]{1, 2, 1},
            new int[]{1, 3, 4},
            new int[]{2, 3, 2}
        );
        int result = kruskalMST(V, edges);
        System.out.println("MST weight: " + result);  // Output: 4
    }
}

JavaScript implementation

class DisjointSet {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }
  find(u) {
    if (this.parent[u] !== u) this.parent[u] = this.find(this.parent[u]);
    return this.parent[u];
  }
  union(u, v) {
    let pu = this.find(u), pv = this.find(v);
    if (pu === pv) return false;
    if (this.rank[pu] < this.rank[pv]) this.parent[pu] = pv;
    else if (this.rank[pu] > this.rank[pv]) this.parent[pv] = pu;
    else {
      this.parent[pv] = pu;
      this.rank[pu]++;
    }
    return true;
  }
}

function kruskalMST(V, edges) {
  edges.sort((a, b) => a[2] - b[2]);
  const dsu = new DisjointSet(V);
  let mstWeight = 0;
  let edgeCount = 0;

  for (const [u, v, w] of edges) {
    if (dsu.union(u, v)) {
      mstWeight += w;
      edgeCount++;
      if (edgeCount === V - 1) break;
    }
  }

  return mstWeight;
}

const edges = [
  [0, 1, 1],
  [0, 2, 3],
  [1, 2, 1],
  [1, 3, 4],
  [2, 3, 2]
];

console.log("MST weight:", kruskalMST(4, edges)); // Output: 4

Go implementation

package main

import (
    "fmt"
    "sort"
)

type DisjointSet struct {
    parent []int
    rank   []int
}

func NewDisjointSet(n int) *DisjointSet {
    parent := make([]int, n)
    rank := make([]int, n)
    for i := 0; i < n; i++ {
        parent[i] = i
    }
    return &DisjointSet{parent, rank}
}

func (ds *DisjointSet) find(u int) int {
    if ds.parent[u] != u {
        ds.parent[u] = ds.find(ds.parent[u])
    }
    return ds.parent[u]
}

func (ds *DisjointSet) union(u, v int) bool {
    pu := ds.find(u)
    pv := ds.find(v)
    if pu == pv {
        return false
    }
    if ds.rank[pu] < ds.rank[pv] {
        ds.parent[pu] = pv
    } else if ds.rank[pu] > ds.rank[pv] {
        ds.parent[pv] = pu
    } else {
        ds.parent[pv] = pu
        ds.rank[pu]++
    }
    return true
}

type Edge struct {
    u, v, weight int
}

func kruskalMST(V int, edges []Edge) int {
    sort.Slice(edges, func(i, j int) bool {
        return edges[i].weight < edges[j].weight
    })

    dsu := NewDisjointSet(V)
    mstWeight := 0
    edgeCount := 0

    for _, e := range edges {
        if dsu.union(e.u, e.v) {
            mstWeight += e.weight
            edgeCount++
            if edgeCount == V-1 {
                break
            }
        }
    }
    return mstWeight
}

func main() {
    V := 4
    edges := []Edge{
        {0, 1, 1},
        {0, 2, 3},
        {1, 2, 1},
        {1, 3, 4},
        {2, 3, 2},
    }
    result := kruskalMST(V, edges)
    fmt.Printf("MST weight: %d\n", result) // Output: 4
}

Rust implementation

use std::cmp::Ordering;

struct DisjointSet {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl DisjointSet {
    fn new(n: usize) -> Self {
        let parent = (0..n).collect();
        let rank = vec![0; n];
        DisjointSet { parent, rank }
    }

    fn find(&mut self, u: usize) -> usize {
        if self.parent[u] != u {
            self.parent[u] = self.find(self.parent[u]);
        }
        self.parent[u]
    }

    fn union(&mut self, u: usize, v: usize) -> bool {
        let pu = self.find(u);
        let pv = self.find(v);
        if pu == pv {
            return false;
        }
        if self.rank[pu] < self.rank[pv] {
            self.parent[pu] = pv;
        } else if self.rank[pu] > self.rank[pv] {
            self.parent[pv] = pu;
        } else {
            self.parent[pv] = pu;
            self.rank[pu] += 1;
        }
        true
    }
}

struct Edge {
    u: usize,
    v: usize,
    weight: i32,
}

fn kruskal_mst(V: usize, mut edges: Vec<Edge>) -> i32 {
    edges.sort_by(|a, b| a.weight.cmp(&b.weight));
    let mut dsu = DisjointSet::new(V);
    let mut mst_weight = 0;
    let mut edge_count = 0;

    for edge in edges {
        if dsu.union(edge.u, edge.v) {
            mst_weight += edge.weight;
            edge_count += 1;
            if edge_count == V - 1 {
                break;
            }
        }
    }
    mst_weight
}

fn main() {
    let V = 4;
    let edges = vec![
        Edge { u: 0, v: 1, weight: 1 },
        Edge { u: 0, v: 2, weight: 3 },
        Edge { u: 1, v: 2, weight: 1 },
        Edge { u: 1, v: 3, weight: 4 },
        Edge { u: 2, v: 3, weight: 2 },
    ];

    let result = kruskal_mst(V, edges);
    println!("MST weight: {}", result); // Output: 4
}

Kotlin implementation

class DisjointSet(n: Int) {
    private val parent = IntArray(n) { it }
    private val rank = IntArray(n) { 0 }

    fun find(u: Int): Int {
        if (parent[u] != u) {
            parent[u] = find(parent[u])
        }
        return parent[u]
    }

    fun union(u: Int, v: Int): Boolean {
        val pu = find(u)
        val pv = find(v)
        if (pu == pv) return false
        when {
            rank[pu] < rank[pv] -> parent[pu] = pv
            rank[pu] > rank[pv] -> parent[pv] = pu
            else -> {
                parent[pv] = pu
                rank[pu]++
            }
        }
        return true
    }
}

fun kruskalMST(V: Int, edges: List<Triple<Int, Int, Int>>): Int {
    val sortedEdges = edges.sortedBy { it.third }
    val dsu = DisjointSet(V)
    var mstWeight = 0
    var edgeCount = 0

    for ((u, v, w) in sortedEdges) {
        if (dsu.union(u, v)) {
            mstWeight += w
            edgeCount++
            if (edgeCount == V - 1) break
        }
    }
    return mstWeight
}

fun main() {
    val V = 4
    val edges = listOf(
        Triple(0, 1, 1),
        Triple(0, 2, 3),
        Triple(1, 2, 1),
        Triple(1, 3, 4),
        Triple(2, 3, 2)
    )
    val result = kruskalMST(V, edges)
    println("MST weight: $result") // Output: 4
}

Swift implementation

class DisjointSet {
    var parent: [Int]
    var rank: [Int]

    init(_ n: Int) {
        parent = Array(0..<n)
        rank = Array(repeating: 0, count: n)
    }

    func find(_ u: Int) -> Int {
        if parent[u] != u {
            parent[u] = find(parent[u])
        }
        return parent[u]
    }

    func union(_ u: Int, _ v: Int) -> Bool {
        let pu = find(u)
        let pv = find(v)
        if pu == pv { return false }

        if rank[pu] < rank[pv] {
            parent[pu] = pv
        } else if rank[pu] > rank[pv] {
            parent[pv] = pu
        } else {
            parent[pv] = pu
            rank[pu] += 1
        }
        return true
    }
}

struct Edge {
    let u: Int
    let v: Int
    let weight: Int
}

func kruskalMST(_ V: Int, _ edges: [Edge]) -> Int {
    let sortedEdges = edges.sorted { $0.weight < $1.weight }
    let dsu = DisjointSet(V)
    var mstWeight = 0
    var edgeCount = 0

    for edge in sortedEdges {
        if dsu.union(edge.u, edge.v) {
            mstWeight += edge.weight
            edgeCount += 1
            if edgeCount == V - 1 { break }
        }
    }
    return mstWeight
}

let V = 4
let edges = [
    Edge(u: 0, v: 1, weight: 1),
    Edge(u: 0, v: 2, weight: 3),
    Edge(u: 1, v: 2, weight: 1),
    Edge(u: 1, v: 3, weight: 4),
    Edge(u: 2, v: 3, weight: 2)
]

print("MST weight: \(kruskalMST(V, edges))") // Output: 4

TypeScript implementation

class DisjointSet {
  parent: number[];
  rank: number[];

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }

  find(u: number): number {
    if (this.parent[u] !== u) this.parent[u] = this.find(this.parent[u]);
    return this.parent[u];
  }

  union(u: number, v: number): boolean {
    const pu = this.find(u);
    const pv = this.find(v);
    if (pu === pv) return false;
    if (this.rank[pu] < this.rank[pv]) this.parent[pu] = pv;
    else if (this.rank[pu] > this.rank[pv]) this.parent[pv] = pu;
    else {
      this.parent[pv] = pu;
      this.rank[pu]++;
    }
    return true;
  }
}

function kruskalMST(V: number, edges: [number, number, number][]): number {
  edges.sort((a, b) => a[2] - b[2]);
  const dsu = new DisjointSet(V);
  let mstWeight = 0;
  let edgeCount = 0;

  for (const [u, v, w] of edges) {
    if (dsu.union(u, v)) {
      mstWeight += w;
      edgeCount++;
      if (edgeCount === V - 1) break;
    }
  }

  return mstWeight;
}

const edges: [number, number, number][] = [
  [0, 1, 1],
  [0, 2, 3],
  [1, 2, 1],
  [1, 3, 4],
  [2, 3, 2]
];

console.log("MST weight:", kruskalMST(4, edges)); // Output: 4