Graph/mst_prim library

🌿 Prim's Algorithm (Minimum Spanning Tree/Forest)

Builds an MST by growing a frontier from an arbitrary start node, always picking the lowest-weight edge crossing the cut.

  • Input: undirected weighted graph adjacency list
  • Time complexity (simple frontier list): O(E log E) worst, O(E·log E) due to sorting
  • Space complexity: O(V + E)

Returns a list of edges in the MST (or MSF for disconnected graphs).

Functions

primMST<T>(Map<T, List<WeightedEdge<T>>> graph) → List<WeightedEdge<T>>