Pattern 24 of 27

Minimum Spanning Tree and Graph Greedy

Connect every node at the lowest total cost by always adding the cheapest edge that does not close a cycle.

Cost: O(E log E) for Kruskal, O(V²) for Prim on a dense graph
Problems: 6

When to reach for it

Every node must end up connected.
The prompt asks for the minimum total cost to connect points or cities.
The best route is judged by its weakest link or its highest single step.

How it works

Kruskal's algorithm sorts edges by weight and adds each one whose endpoints are not yet connected, using union find to check. Prim's algorithm grows one tree and always attaches the cheapest outside node, which suits dense graphs where every pair of points is an edge. Several related problems ask for a bottleneck path, where the answer is the weakest edge on the best route; adding cells or edges in sorted order until the two ends connect solves them with the same union find.

The template

Written for Min Cost to Connect All Points (write-up)

def min_cost_connect_points(points):
    n = len(points)
    best = [float("inf")] * n         # cheapest edge into the tree so far
    best[0] = 0
    in_tree = [False] * n
    total = 0
    for _ in range(n):
        u = min((i for i in range(n) if not in_tree[i]), key=best.__getitem__)
        in_tree[u] = True
        total += best[u]
        for v in range(n):
            if not in_tree[v]:
                d = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1])
                best[v] = min(best[v], d)
    return total

Open in the editor Trace it line by line

Six problems, in learning order

1.Min Cost to Connect All PointsLeetCode 1584Prim over the implicit complete graph of points.Medium
2.Connecting Cities With Minimum CostLeetCode 1135PremiumKruskal with union find; return -1 if the cities never all connect.Not in the curated 370 yet.Medium
3.Optimize Water Distribution in a VillageLeetCode 1168PremiumAdd a virtual node whose edges cost what each well costs.Not in the curated 370 yet.Hard
4.Find Critical and Pseudo-Critical Edges in Minimum Spanning TreeLeetCode 1489Recompute the tree weight without each edge, and again with each edge forced in.Not in the curated 370 yet.Hard
5.Swim in Rising WaterLeetCode 778Add cells in order of height until the two corners connect.Hard
6.Path With Maximum Minimum ValueLeetCode 1102PremiumAdd cells from highest value to lowest until the two corners connect.Not in the curated 370 yet.Medium

What usually goes wrong

Building all V² edges for Kruskal on a dense point set when Prim is simpler.
Forgetting that a disconnected graph has no spanning tree.
Confusing a minimum spanning tree with a shortest path tree; they answer different questions.

Minimum Spanning Tree and Graph Greedy, answered

When should I use the minimum spanning tree and graph greedy pattern?

Every node must end up connected. The prompt asks for the minimum total cost to connect points or cities. The best route is judged by its weakest link or its highest single step.

What is the time complexity of minimum spanning tree and graph greedy?

O(E log E) for Kruskal, O(V²) for Prim on a dense graph. Several related problems ask for a bottleneck path, where the answer is the weakest edge on the best route; adding cells or edges in sorted order until the two ends connect solves them with the same union find.

Which problem should I start with for minimum spanning tree and graph greedy?

Start with Min Cost to Connect All Points (LeetCode 1584, Medium). Prim over the implicit complete graph of points. The six problems on this page are in learning order.