Module mst 

Minimum spanning tree via Prim’s and Kruskal’s algorithms.

Both require an undirected graph, ignore self-loops, and break ties deterministically by (weight, min endpoint, max endpoint, edge id). Each returns a SpanningTree whose edge ids are sorted ascending, so the two algorithms produce comparable witnesses.

Traits

MstWeight

Integer weights that can report overflow while summing MST totals.

Functions

kruskals_mst

Kruskal’s algorithm: sort edges, union-find to reject cycles.

prims_mst

Prim’s algorithm: grow a tree from node 0 using a min-heap keyed on the same deterministic tie-break as Kruskal.