templates · Shortest paths & spanning trees

Prim's minimum spanning tree

  • "Connect all points / cities / computers at the minimum total cost"
  • Every node must be joined, and any cycle would only waste money
  • The graph is dense, or given as points where every pair is an edge

Minimum spanning tree (Kruskal / Prim)

the one rule

The invariant

The nodes marked inTree always form one tree, and the next node added is the one joined by the cheapest edge leaving that tree.

write it from memory

The template

Prim with a heap (adjacency list)

javajava.util.*
/** Total weight of a minimum spanning tree. edges[i] = {u, v, w}, undirected. -1 = graph not connected. */static long primMst(int n, int[][] edges) {    List<List<int[]>> adj = new ArrayList<>();    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());    for (int[] e : edges) {                           // undirected: store both ways        adj.get(e[0]).add(new int[] {e[1], e[2]});        adj.get(e[1]).add(new int[] {e[0], e[2]});    }    boolean[] inTree = new boolean[n];    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1])); // {node, weight}    heap.add(new int[] {0, 0});                       // start from any node    long total = 0;    int added = 0;    while (!heap.isEmpty() && added < n) {        int[] top = heap.poll();                      // cheapest edge leaving the tree        int u = top[0];        if (inTree[u]) continue;                      // stale entry: u joined already        inTree[u] = true;        total += top[1];        added++;        for (int[] next : adj.get(u))            if (!inTree[next[0]]) heap.add(next);     // edges from the new node    }    return added == n ? total : -1;}

"Lazy" means old heap entries are not removed; we just skip a node that is already in the tree. Same shape as Dijkstra, but the key is one edge's weight, not the distance from the start.

fill in the blanks — only these lines change per problem

  1. line 5How you build the graph: from an edge list, a matrix, or points.
  2. line 19What you collect when a node joins: the total cost, or the edge itself if the tree must be returned.
  3. line 24What to return if some node was never reached (the graph is not connected).

Prim without a heap (every pair is an edge)

javajava.util.*
/** Min cost to connect all points (Manhattan distance). O(n²) Prim with no heap: best for a complete graph. */static int minCostConnectPoints(int[][] points) {    int n = points.length;    int[] best = new int[n];                          // cheapest edge from the tree to each point    Arrays.fill(best, Integer.MAX_VALUE);    if (n > 0) best[0] = 0;    boolean[] inTree = new boolean[n];    int total = 0;    for (int round = 0; round < n; round++) {        int u = -1;        for (int i = 0; i < n; i++)                   // the closest point outside the tree            if (!inTree[i] && (u == -1 || best[i] < best[u])) u = i;        inTree[u] = true;        total += best[u];        for (int v = 0; v < n; v++) {            if (inTree[v]) continue;            int w = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);            if (w < best[v]) best[v] = w;        }    }    return total;}

For n points with an edge between every pair, E ≈ n²/2. Scanning one array is simpler and faster than a heap here.

fill in the blanks — only these lines change per problem

  1. line 17The edge weight between two points: Manhattan distance here, but it could be any formula.
  2. line 11Which node joins next: the cheapest one outside the tree.

complexity

What it costs

time O(E log E) with a heap · O(V²) dense
With a heap, each edge is pushed at most once (when the first of its two ends joins the tree), so there are at most E pushes and polls, each costing log E. The dense version scans all V nodes, V times, with no heap.
space O(V + E)
The adjacency list and the heap. The dense version needs only O(V): one best array.

watch out

Common bugs

  • Not skipping a node that is already inTree. Then its edge is counted twice and the total is too big.
  • Keying the heap by distance from the start (that is Dijkstra). Prim keys by the weight of the single edge.
  • Using -1 for "not connected" when weights can be negative, so a real total of -1 looks like failure.

use it

Practise it on

learn it properly