Minimum Spanning Tree

Not started yet — 4 problems queued.

An MST connects all nodes with minimum total edge weight and no cycles. Kruskal's sorts edges and adds one if it doesn't form a cycle (via Union-Find) — good for sparse graphs. Prim's grows the tree from a start node, always adding the cheapest edge to an unvisited node via a min-heap — good for dense graphs.

Sub-patterns

A — Kruskal's. Edge-sorted, grown via Union-Find.
B — Prim's. Heap-grown from a start node.

Practice set (4)

Medium — Min Cost to Connect All Points, Connecting Cities With Minimum Cost (Premium)
Hard — Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree, Optimize Water Distribution in a Village (Premium)

Pending

Kruskal's

Sort all edges by weight, add each one if it doesn't form a cycle — good for sparse graphs.

Pending

Prim's

Grow the tree from a start node, always adding the cheapest edge to an unvisited node via a min-heap — good for dense graphs.

Notes from readers

Comments — via GitHub