yog/mst

Minimum Spanning Tree (MST) algorithms for finding optimal network connections.

A Minimum Spanning Tree connects all nodes in a weighted undirected graph with the minimum possible total edge weight. MSTs have applications in network design, clustering, and optimization problems.

Available Algorithms

Algorithm	Function	Best For
Kruskal’s	`kruskal/2`	Sparse graphs, edge lists

Properties of MSTs

Connects all nodes with exactly V - 1 edges (for a graph with V nodes)
Contains no cycles
Minimizes the sum of edge weights
May not be unique if multiple edges have the same weight

Example Use Cases

Network Design: Minimizing cable length to connect buildings
Cluster Analysis: Hierarchical clustering via MST
Approximation: Traveling Salesman Problem approximations
Image Segmentation: Computer vision applications

References

Types

Edge

</>

Represents an edge in the minimum spanning tree.

pub type Edge(e) {
  Edge(from: Int, to: Int, weight: e)
}

Constructors

```
Edge(from: Int, to: Int, weight: e)
```

Values

kruskal

</>

pub fn kruskal(
  in graph: model.Graph(n, e),
  with_compare compare: fn(e, e) -> order.Order,
) -> List(Edge(e))

Finds the Minimum Spanning Tree (MST) using Kruskal’s algorithm.

Returns a list of edges that form the MST. The total weight of these edges is minimized while ensuring all nodes are connected.

Time Complexity: O(E log E) where E is the number of edges

Example

let mst_edges = mst.kruskal(in: graph, with_compare: int.compare)
// => [Edge(1, 2, 5), Edge(2, 3, 3), ...]

prim

</>

pub fn prim(
  in graph: model.Graph(n, e),
  with_compare compare: fn(e, e) -> order.Order,
) -> List(Edge(e))

Finds the Minimum Spanning Tree (MST) using Prim’s algorithm.

Returns a list of edges that form the MST. Unlike Kruskal’s which processes all edges globally, Prim’s grows the MST from a starting node by repeatedly adding the minimum-weight edge that connects a visited node to an unvisited node.

Time Complexity: O(E log V) where E is the number of edges and V is the number of vertices

Example

let mst_edges = mst.prim(in: graph, with_compare: int.compare)
// => [Edge(1, 2, 5), Edge(2, 3, 3), ...]