802 Fundamental

802-kruskals-mst — Kruskal's Minimum Spanning Tree

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "802-kruskals-mst — Kruskal's Minimum Spanning Tree" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Kruskal's algorithm (1956) finds the MST by sorting all edges by weight and adding each edge if it doesn't create a cycle, using a Union-Find (Disjoint Set Union) data structure to detect cycles in near-O(1). Key difference from OCaml: 1. **Union

Tutorial

The Problem

Kruskal's algorithm (1956) finds the MST by sorting all edges by weight and adding each edge if it doesn't create a cycle, using a Union-Find (Disjoint Set Union) data structure to detect cycles in near-O(1). While Prim's grows from a vertex, Kruskal's grows from edges. It is more efficient for sparse graphs (E ≈ V) and is the basis for Borůvka's parallel MST algorithm used in distributed computing.

🎯 Learning Outcomes

• Implement Union-Find with path compression and union by rank

• Sort edges by weight and process them greedily

• Skip edges whose endpoints are in the same component (would create a cycle)

• Understand O(E log E) time complexity (dominated by sorting)

• See how Union-Find achieves near-O(1) amortized per operation with path compression

Code Example

#![allow(clippy::all)]
//! # Kruskal's MST Algorithm

pub struct UnionFind {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl UnionFind {
    pub fn new(n: usize) -> Self {
        Self {
            parent: (0..n).collect(),
            rank: vec![0; n],
        }
    }
    pub fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.parent[x] = self.find(self.parent[x]);
        }
        self.parent[x]
    }
    pub fn union(&mut self, x: usize, y: usize) -> bool {
        let (px, py) = (self.find(x), self.find(y));
        if px == py {
            return false;
        }
        match self.rank[px].cmp(&self.rank[py]) {
            std::cmp::Ordering::Less => self.parent[px] = py,
            std::cmp::Ordering::Greater => self.parent[py] = px,
            std::cmp::Ordering::Equal => {
                self.parent[py] = px;
                self.rank[px] += 1;
            }
        }
        true
    }
}

pub fn kruskals_mst(n: usize, edges: &mut [(usize, usize, i32)]) -> i32 {
    edges.sort_by_key(|e| e.2);
    let mut uf = UnionFind::new(n);
    let mut total = 0;
    for &(u, v, w) in edges.iter() {
        if uf.union(u, v) {
            total += w;
        }
    }
    total
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_kruskals() {
        let mut edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)];
        assert_eq!(kruskals_mst(4, &mut edges), 19);
    }
}

(* Kruskal's MST — sort + Union-Find O(E log E) *)

(* Union-Find with path compression and union by rank *)
let make_uf n =
  let parent = Array.init n (fun i -> i) in
  let rank   = Array.make n 0 in
  (parent, rank)

let rec find parent v =
  if parent.(v) = v then v
  else begin
    parent.(v) <- find parent parent.(v);  (* path compression *)
    parent.(v)
  end

let union parent rank u v =
  let pu = find parent u and pv = find parent v in
  if pu = pv then false
  else begin
    if rank.(pu) < rank.(pv) then parent.(pu) <- pv
    else if rank.(pu) > rank.(pv) then parent.(pv) <- pu
    else begin parent.(pv) <- pu; rank.(pu) <- rank.(pu) + 1 end;
    true
  end

let kruskal n edges =
  (* edges: (weight, u, v) list *)
  let sorted = List.sort (fun (w1,_,_) (w2,_,_) -> compare w1 w2) edges in
  let (parent, rank) = make_uf n in
  List.fold_left (fun (total, mst) (w, u, v) ->
    if union parent rank u v then
      (total + w, (u, v, w) :: mst)
    else
      (total, mst)
  ) (0, []) sorted

let () =
  let edges = [
    (2, 0, 1); (6, 0, 3);
    (3, 1, 2); (8, 1, 3); (5, 1, 4);
    (7, 2, 4); (9, 3, 4)
  ] in
  let (total, mst) = kruskal 5 edges in
  Printf.printf "MST total weight: %d\n" total;
  List.iter (fun (u, v, w) ->
    Printf.printf "  edge %d-%d  weight=%d\n" u v w
  ) (List.rev mst)

Key Differences

Union-Find ergonomics: Rust's struct UnionFind with methods is idiomatic; OCaml uses a module with mutable arrays, similar in structure.

Path compression: Both languages implement the two-pass path compression the same way; Rust's recursive implementation matches OCaml's.

Sorting: Rust's Vec::sort_by_key and OCaml's Array.sort are both O(n log n); the edge comparison is identical.

Parallel MST: Borůvka's algorithm (more parallelizable than Kruskal's) is used in distributed graph processing (Apache Spark GraphX); Kruskal's is the sequential baseline.

OCaml Approach

OCaml's Union-Find uses Array.make n (Array.init n Fun.id) for the parent array and imperative updates. The path compression is expressed as a recursive function with a ref for the root. OCaml's Array.sort sorts edges in-place. The Ocamlgraph.Kruskal module provides a clean functional implementation using persistent data structures.

Full Source

#![allow(clippy::all)]
//! # Kruskal's MST Algorithm

pub struct UnionFind {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl UnionFind {
    pub fn new(n: usize) -> Self {
        Self {
            parent: (0..n).collect(),
            rank: vec![0; n],
        }
    }
    pub fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.parent[x] = self.find(self.parent[x]);
        }
        self.parent[x]
    }
    pub fn union(&mut self, x: usize, y: usize) -> bool {
        let (px, py) = (self.find(x), self.find(y));
        if px == py {
            return false;
        }
        match self.rank[px].cmp(&self.rank[py]) {
            std::cmp::Ordering::Less => self.parent[px] = py,
            std::cmp::Ordering::Greater => self.parent[py] = px,
            std::cmp::Ordering::Equal => {
                self.parent[py] = px;
                self.rank[px] += 1;
            }
        }
        true
    }
}

pub fn kruskals_mst(n: usize, edges: &mut [(usize, usize, i32)]) -> i32 {
    edges.sort_by_key(|e| e.2);
    let mut uf = UnionFind::new(n);
    let mut total = 0;
    for &(u, v, w) in edges.iter() {
        if uf.union(u, v) {
            total += w;
        }
    }
    total
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_kruskals() {
        let mut edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)];
        assert_eq!(kruskals_mst(4, &mut edges), 19);
    }
}

(* Kruskal's MST — sort + Union-Find O(E log E) *)

(* Union-Find with path compression and union by rank *)
let make_uf n =
  let parent = Array.init n (fun i -> i) in
  let rank   = Array.make n 0 in
  (parent, rank)

let rec find parent v =
  if parent.(v) = v then v
  else begin
    parent.(v) <- find parent parent.(v);  (* path compression *)
    parent.(v)
  end

let union parent rank u v =
  let pu = find parent u and pv = find parent v in
  if pu = pv then false
  else begin
    if rank.(pu) < rank.(pv) then parent.(pu) <- pv
    else if rank.(pu) > rank.(pv) then parent.(pv) <- pu
    else begin parent.(pv) <- pu; rank.(pu) <- rank.(pu) + 1 end;
    true
  end

let kruskal n edges =
  (* edges: (weight, u, v) list *)
  let sorted = List.sort (fun (w1,_,_) (w2,_,_) -> compare w1 w2) edges in
  let (parent, rank) = make_uf n in
  List.fold_left (fun (total, mst) (w, u, v) ->
    if union parent rank u v then
      (total + w, (u, v, w) :: mst)
    else
      (total, mst)
  ) (0, []) sorted

let () =
  let edges = [
    (2, 0, 1); (6, 0, 3);
    (3, 1, 2); (8, 1, 3); (5, 1, 4);
    (7, 2, 4); (9, 3, 4)
  ] in
  let (total, mst) = kruskal 5 edges in
  Printf.printf "MST total weight: %d\n" total;
  List.iter (fun (u, v, w) ->
    Printf.printf "  edge %d-%d  weight=%d\n" u v w
  ) (List.rev mst)

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_kruskals() {
        let mut edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)];
        assert_eq!(kruskals_mst(4, &mut edges), 19);
    }
}

Deep Comparison

OCaml vs Rust: Kruskals Mst

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Modify to return the actual MST edges Vec<(usize, usize, i32)>, not just the total weight.

Implement max_spanning_tree by reversing the edge sort order — identical to Kruskal's but taking maximum-weight edges.

Implement an online Kruskal's that accepts edges one at a time and reports the current spanning forest weight after each insertion.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust