yog/mst

Types

Represents an edge in the minimum spanning tree.

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

</>

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

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