MST

Minimum Spanning Tree algorithms: Prim's and Kruskal's.

A Minimum Spanning Tree (MST) of a connected undirected weighted graph is a subset of edges that connects all vertices with the minimum total edge weight and contains no cycles.

Both algorithms produce the same optimal result and return an array of Edge values.

When to use each variant

Algorithm	Best when
prim	Dense graphs; start vertex is known
kruskal	Sparse graphs; all vertices known upfront

All functions accept either callback form for GetNeighbors — see GraphUtil for details.

Undirected graphs

Both algorithms expect an undirected graph where each edge is represented in both directions by getNeighbors (i.e. if A is a neighbour of B, then B must also be a neighbour of A).

Example graph

--       1
--  A ─────── B
--  │ ╲       │
--  4  ╲3     2
--  │    ╲    │
--  D ─────── C
--       5

local weights = {
    A = {B=1, C=3, D=4},
    B = {A=1, C=2},
    C = {B=2, A=3, D=5},
    D = {A=4, C=5},
}
local allVertices = {"A","B","C","D"}

local function getNeighbors(v)
    local result = {}
    for k in pairs(weights[v]) do table.insert(result, k) end
    return result
end
local function getWeight(u, v) return weights[u][v] end

Functions

prim

undirected

</>

MST.prim(

start: V,

getNeighbors: GetNeighbors<V>,

getWeight: GetWeight<V>

) → {Edge<V>}

Builds a Minimum Spanning Tree starting from start using Prim's algorithm with a min-heap. Returns an array of Edge values whose total weight is minimised.

The function grows the MST greedily: it always picks the cheapest edge crossing from the visited set into the unvisited set.

local edges = MST.prim("A", getNeighbors, getWeight)
-- {
--   { from="A", to="B", weight=1 },
--   { from="B", to="C", weight=2 },
--   { from="A", to="D", weight=4 },  -- (A-D cheaper than C-D)
-- }

Connectivity

If the graph is disconnected, prim only spans the component reachable from start. Run once per component to span the full forest.

Time complexity: O((V + E) log V) with a binary min-heap.

kruskal

undirected

</>

MST.kruskal(

allVertices: {V},

getNeighbors: GetNeighbors<V>,

getWeight: GetWeight<V>

) → {Edge<V>}

Builds a Minimum Spanning Tree using Kruskal's algorithm. Returns an array of Edge values whose total weight is minimised.

Kruskal's works by sorting all edges by weight and greedily adding each edge that connects two previously disconnected components, using a Union-Find (disjoint-set) structure to detect cycles in O(α(V)) time.

local edges = MST.kruskal(allVertices, getNeighbors, getWeight)
-- {
--   { from="A", to="B", weight=1 },
--   { from="B", to="C", weight=2 },
--   { from="A", to="D", weight=4 },
-- }

Edge discovery

Kruskal's collects all edges by iterating getNeighbors over every vertex in allVertices. To avoid duplicates, each undirected edge is only added once (the canonical direction is the one where the vertex appears first in allVertices).

Time complexity: O(E log E) dominated by the edge sort.