Minimum Spanning Trees (Prim / Kruskal)

A minimum spanning tree (MST) is a subset of edges in a connected, weighted, undirected graph that connects all vertices with the minimum possible total edge weight, without forming any cycles.

Minimum spanning trees are widely used in network design, clustering, and optimization problems.

What Is a Spanning Tree?

Given a graph with V vertices:

• A spanning tree connects all vertices
• It contains exactly V − 1 edges
• It has no cycles

Among all possible spanning trees, the minimum spanning tree has the smallest total weight.

Key Properties of MST

• Works only on undirected graphs
• Graph must be connected
• If the graph is disconnected, an MST does not exist (you get a forest instead)
• Multiple MSTs may exist if edge weights are equal

Example Graph

    (1)
 A ------- B
 | \       |
4|  \2     |5
 |   \     |
 C ------- D
      3

One possible MST:

A -- B (1)
A -- C (4)
C -- D (3)
Total weight = 8

Two Common MST Algorithms

Minimum spanning trees are typically computed using:

1. Prim’s Algorithm
2. Kruskal’s Algorithm

Both run efficiently and produce the same total weight, though their strategies differ.

Prim’s Algorithm

Idea

Prim’s algorithm builds the MST by:

• Starting from an arbitrary vertex
• Repeatedly adding the minimum-weight edge that connects the tree to a new vertex

It grows the MST one vertex at a time.

When to Use Prim’s Algorithm

• Graph is dense
• Adjacency list + priority queue available
• You want a vertex-centric approach

Rust Implementation (Prim’s Algorithm)

use std::collections::{BinaryHeap, HashMap, HashSet};
use std::cmp::Reverse;

type Graph = HashMap<i32, Vec<(i32, i32)>>;

pub fn prim_mst(graph: &Graph, start: i32) -> Vec<(i32, i32, i32)> {
    let mut visited = HashSet::new();
    let mut heap = BinaryHeap::new();
    let mut mst = Vec::new();

    visited.insert(start);

    if let Some(neighbors) = graph.get(&start) {
        for &(to, weight) in neighbors {
            heap.push(Reverse((weight, start, to)));
        }
    }

    while let Some(Reverse((weight, from, to))) = heap.pop() {
        if visited.contains(&to) {
            continue;
        }

        visited.insert(to);
        mst.push((from, to, weight));

        if let Some(neighbors) = graph.get(&to) {
            for &(next, w) in neighbors {
                if !visited.contains(&next) {
                    heap.push(Reverse((w, to, next)));
                }
            }
        }
    }

    mst
}

Example Usage

fn main() {
    let mut graph: Graph = HashMap::new();

    graph.insert(1, vec![(2, 1), (3, 4)]);
    graph.insert(2, vec![(1, 1), (3, 2), (4, 5)]);
    graph.insert(3, vec![(1, 4), (2, 2), (4, 3)]);
    graph.insert(4, vec![(2, 5), (3, 3)]);

    let mst = prim_mst(&graph, 1);

    let total_weight: i32 = mst.iter().map(|(_, _, w)| *w).sum();
    println!("MST edges: {:?}", mst);
    println!("Total weight: {}", total_weight);
}

Kruskal’s Algorithm

Idea

Kruskal’s algorithm builds the MST by:

• Sorting all edges by weight
• Adding edges one by one
• Skipping edges that would form a cycle

It uses a Disjoint Set (Union-Find) data structure.

When to Use Kruskal’s Algorithm

• Graph is sparse
• Edge list representation
• Easy cycle detection with Union-Find

Rust Implementation (Kruskal’s Algorithm)

use std::collections::HashMap;

#[derive(Debug, Clone)]
pub struct Edge {
    pub u: i32,
    pub v: i32,
    pub weight: i32,
}

struct UnionFind {
    parent: HashMap<i32, i32>,
    rank: HashMap<i32, i32>,
}

impl UnionFind {
    fn new(vertices: &[i32]) -> Self {
        let mut parent = HashMap::new();
        let mut rank = HashMap::new();

        for &v in vertices {
            parent.insert(v, v);
            rank.insert(v, 0);
        }

        UnionFind { parent, rank }
    }

    fn find(&mut self, x: i32) -> i32 {
        let parent = self.parent[&x];
        if parent != x {
            let root = self.find(parent);
            self.parent.insert(x, root);
        }
        self.parent[&x]
    }

    fn union(&mut self, x: i32, y: i32) -> bool {
        let x_root = self.find(x);
        let y_root = self.find(y);

        if x_root == y_root {
            return false;
        }

        let x_rank = self.rank[&x_root];
        let y_rank = self.rank[&y_root];

        if x_rank < y_rank {
            self.parent.insert(x_root, y_root);
        } else if x_rank > y_rank {
            self.parent.insert(y_root, x_root);
        } else {
            self.parent.insert(y_root, x_root);
            *self.rank.get_mut(&x_root).unwrap() += 1;
        }

        true
    }
}

pub fn kruskal_mst(vertices: &[i32], edges: &mut Vec<Edge>) -> Vec<Edge> {
    edges.sort_by_key(|e| e.weight);

    let mut uf = UnionFind::new(vertices);
    let mut mst = Vec::new();

    for edge in edges.iter() {
        if uf.union(edge.u, edge.v) {
            mst.push(edge.clone());
        }
    }

    mst
}

Example Usage

fn main() {
    let graph: Graph = HashMap::from([
        (1, vec![(2, 1), (3, 4)]),
        (2, vec![(1, 1), (3, 2), (4, 5)]),
        (3, vec![(1, 4), (2, 2), (4, 3)]),
        (4, vec![(2, 5), (3, 3)]),
    ]);

    let vertices: Vec<i32> = graph.keys().cloned().collect();

    let mut edges = Vec::new();
    for (&u, neighbors) in &graph {
        for &(v, w) in neighbors {
            if u < v {
                edges.push(Edge {
                    u,
                    v,
                    weight: w,
                });
            }
        }
    }

    let mst = kruskal_mst(&vertices, &mut edges);

    let total_weight: i32 = mst.iter().map(|e| e.weight).sum();

    println!("MST edges: {:?}", mst);
    println!("Total weight: {}", total_weight);
}

Time and Space Complexity

Time Complexity

Space Complexity

Prim vs Kruskal

Summary

• MST connects all vertices with minimum total weight
• No cycles allowed
• Prim is vertex-based
• Kruskal is edge-based
• Both guarantee optimal MST

Playground Links

Rust - Prim's Algorithm

Rust - Kruskal’s Algorithm