yog/mst

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), ...]