← Back to the graphs page
Weighted Undirected Graph → Minimum Spanning Tree
Connect all nodes with minimum total edge weight and no cycles. The result is always a tree with exactly V−1 edges.
What to know
- Kruskal sorts edges globally and unions components — great for sparse graphs and edge lists.
- Prim grows one tree outward with a heap — great when adjacency lists are already built.
- The cut property proves both: the lightest edge crossing any cut belongs to some MST.
- If all edge weights are distinct the MST is unique.
In the wild: Laying fiber/electric cable at minimum cost, network design, clustering (single-linkage).
Algorithms to reach for
Kruskal + Union-Find
O(E log E)MST from a sorted edge list
Prim + min-heap
O(E log V)MST grown from a start node
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.