801 Fundamental

801-prims-mst — Prim's Minimum Spanning Tree

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "801-prims-mst — Prim's Minimum Spanning Tree" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. A Minimum Spanning Tree (MST) of a weighted undirected graph connects all vertices with minimum total edge weight. Key difference from OCaml: 1. **Priority queue**: Rust's `BinaryHeap<Reverse<...>>` is a max

Tutorial

The Problem

A Minimum Spanning Tree (MST) of a weighted undirected graph connects all vertices with minimum total edge weight. Prim's algorithm (1957) grows the MST greedily from a starting vertex, always adding the cheapest edge connecting the MST to a new vertex. MSTs are used in network design (laying cables or pipes with minimum cost), cluster analysis, and approximation algorithms for traveling salesman.

🎯 Learning Outcomes

• Use a min-heap (BinaryHeap<Reverse<(weight, vertex)>>) to always select the cheapest edge

• Mark vertices as visited to avoid cycles

• Build the adjacency list representation from edge list

• Understand the O((V+E)logV) time complexity with a binary heap

• Compare with Kruskal's: Prim's is better for dense graphs, Kruskal's for sparse

Code Example

#![allow(clippy::all)]
//! # Prim's MST Algorithm
use std::cmp::Reverse;
use std::collections::BinaryHeap;

pub fn prims_mst(n: usize, edges: &[(usize, usize, i32)]) -> i32 {
    let mut adj = vec![vec![]; n];
    for &(u, v, w) in edges {
        adj[u].push((v, w));
        adj[v].push((u, w));
    }
    let mut visited = vec![false; n];
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0, 0)));
    let mut total = 0;

    while let Some(Reverse((w, u))) = heap.pop() {
        if visited[u] {
            continue;
        }
        visited[u] = true;
        total += w;
        for &(v, wt) in &adj[u] {
            if !visited[v] {
                heap.push(Reverse((wt, v)));
            }
        }
    }
    total
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_prims() {
        let edges = [(0, 1, 4), (0, 7, 8), (1, 2, 8), (1, 7, 11)];
        assert!(prims_mst(8, &edges) > 0);
    }
}

(* Prim's MST — O(V²) with linear scan (clean, readable) *)

let prim adj n =
  let key    = Array.make n max_int in
  let parent = Array.make n (-1) in
  let inMST  = Array.make n false in
  key.(0) <- 0;
  let total = ref 0 in
  let mst   = ref [] in
  for _ = 0 to n - 1 do
    (* Find unvisited vertex with minimum key *)
    let u = ref (-1) in
    for v = 0 to n - 1 do
      if not inMST.(v) && key.(v) < max_int then
        if !u = -1 || key.(v) < key.(!u) then u := v
    done;
    if !u >= 0 then begin
      inMST.(!u) <- true;
      if parent.(!u) >= 0 then begin
        total := !total + key.(!u);
        mst   := (!u, parent.(!u), key.(!u)) :: !mst
      end;
      List.iter (fun (w, v) ->
        if not inMST.(v) && w < key.(v) then begin
          key.(v)    <- w;
          parent.(v) <- !u
        end
      ) adj.(!u)
    end
  done;
  (!total, List.rev !mst)

let () =
  (* Undirected graph as adjacency list: adj.(u) = [(weight, v); ...] *)
  let adj = Array.make 5 [] in
  let add_edge u v w =
    adj.(u) <- (w, v) :: adj.(u);
    adj.(v) <- (w, u) :: adj.(v)
  in
  add_edge 0 1 2; add_edge 0 3 6;
  add_edge 1 2 3; add_edge 1 3 8; add_edge 1 4 5;
  add_edge 2 4 7;
  add_edge 3 4 9;
  let (total, mst) = prim adj 5 in
  Printf.printf "MST total weight: %d\n" total;
  List.iter (fun (u, v, w) ->
    Printf.printf "  edge %d-%d  weight=%d\n" v u w
  ) mst

Key Differences

Priority queue: Rust's BinaryHeap<Reverse<...>> is a max-heap turned into a min-heap via Reverse; OCaml uses Set as a BST-based priority queue.

Immutable traversal: OCaml can express Prim's as a fold over priority queue states; Rust's imperative while-loop is more straightforward.

Dense vs sparse: For dense graphs (E ≈ V²), Prim's with an array-based priority queue achieves O(V²) — faster than the heap variant; both languages support this.

Network design: Real cable-laying optimization uses MST as a lower bound, then adds fault tolerance — a topic in telecommunications engineering.

OCaml Approach

OCaml uses Map or Hashtbl for adjacency lists and Set as a priority queue (OCaml's set is a balanced BST, giving O(log n) min extraction). Alternatively, module PQueue = Set.Make(...) serves as a min-heap. The Ocamlgraph library provides Kruskal and Prim implementations. OCaml's Array.iteri can build adjacency lists from edge arrays efficiently.

Full Source

#![allow(clippy::all)]
//! # Prim's MST Algorithm
use std::cmp::Reverse;
use std::collections::BinaryHeap;

pub fn prims_mst(n: usize, edges: &[(usize, usize, i32)]) -> i32 {
    let mut adj = vec![vec![]; n];
    for &(u, v, w) in edges {
        adj[u].push((v, w));
        adj[v].push((u, w));
    }
    let mut visited = vec![false; n];
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0, 0)));
    let mut total = 0;

    while let Some(Reverse((w, u))) = heap.pop() {
        if visited[u] {
            continue;
        }
        visited[u] = true;
        total += w;
        for &(v, wt) in &adj[u] {
            if !visited[v] {
                heap.push(Reverse((wt, v)));
            }
        }
    }
    total
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_prims() {
        let edges = [(0, 1, 4), (0, 7, 8), (1, 2, 8), (1, 7, 11)];
        assert!(prims_mst(8, &edges) > 0);
    }
}

(* Prim's MST — O(V²) with linear scan (clean, readable) *)

let prim adj n =
  let key    = Array.make n max_int in
  let parent = Array.make n (-1) in
  let inMST  = Array.make n false in
  key.(0) <- 0;
  let total = ref 0 in
  let mst   = ref [] in
  for _ = 0 to n - 1 do
    (* Find unvisited vertex with minimum key *)
    let u = ref (-1) in
    for v = 0 to n - 1 do
      if not inMST.(v) && key.(v) < max_int then
        if !u = -1 || key.(v) < key.(!u) then u := v
    done;
    if !u >= 0 then begin
      inMST.(!u) <- true;
      if parent.(!u) >= 0 then begin
        total := !total + key.(!u);
        mst   := (!u, parent.(!u), key.(!u)) :: !mst
      end;
      List.iter (fun (w, v) ->
        if not inMST.(v) && w < key.(v) then begin
          key.(v)    <- w;
          parent.(v) <- !u
        end
      ) adj.(!u)
    end
  done;
  (!total, List.rev !mst)

let () =
  (* Undirected graph as adjacency list: adj.(u) = [(weight, v); ...] *)
  let adj = Array.make 5 [] in
  let add_edge u v w =
    adj.(u) <- (w, v) :: adj.(u);
    adj.(v) <- (w, u) :: adj.(v)
  in
  add_edge 0 1 2; add_edge 0 3 6;
  add_edge 1 2 3; add_edge 1 3 8; add_edge 1 4 5;
  add_edge 2 4 7;
  add_edge 3 4 9;
  let (total, mst) = prim adj 5 in
  Printf.printf "MST total weight: %d\n" total;
  List.iter (fun (u, v, w) ->
    Printf.printf "  edge %d-%d  weight=%d\n" v u w
  ) mst

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_prims() {
        let edges = [(0, 1, 4), (0, 7, 8), (1, 2, 8), (1, 7, 11)];
        assert!(prims_mst(8, &edges) > 0);
    }
}

Deep Comparison

OCaml vs Rust: Prims 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 the algorithm to also return the MST edges (not just the total weight), storing (u, v, weight) triples.

Implement Prim's with an indexed priority queue (decrease-key operation) to achieve O((V+E)logV) without duplicate heap entries.

Compare Prim's and Kruskal's (example 802) on the same graph and verify they produce the same total weight (MSTs are not unique but have equal weight).

Open Source Repos

functional-rust

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

Rust