Topics › Graphs › MinimumSpanningTree/Disjoint Set and Problems

MST using Prim's Algo

Hard TUF ID 2824 SDE

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an undirected weighted graph with V vertices numbered 0 to V - 1 and a list of edges {u, v, w}. A spanning tree is a set of V - 1 edges that connects all vertices without forming a cycle. Return the total weight of a minimum spanning tree (MST), the spanning tree with the smallest sum of edge weights. The sheet’s version (GFG, “Minimum Spanning Tree”) guarantees a connected graph; the code here returns -1 when the graph is disconnected and no spanning tree exists. We also show how to return the tree’s edges, not just its weight.

Constraints in the usual version: V up to about 1000, E up to V(V - 1) / 2, positive weights up to about 1000.

Example 1

V = 3, edges = [0-1 (5), 1-2 (3), 0-2 (1)]
answer = 4          // take 0-2 (1) and 1-2 (3); adding 0-1 (5) would close a cycle

Example 2

V = 5, edges = [0-1 (2), 0-3 (6), 1-2 (3), 1-3 (8), 1-4 (5), 2-4 (7), 3-4 (9)]
answer = 16         // 0-1 (2) + 1-2 (3) + 1-4 (5) + 0-3 (6)

The graph is stored as an adjacency list of {neighbour, weight} pairs, each edge in both directions:

static List<List<int[]>> buildAdj(int V, int[][] edges) {
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(new int[]{e[1], e[2]});
        adj.get(e[1]).add(new int[]{e[0], e[2]});
    }
    return adj;
}

Approach 1: Brute force, try every set of V - 1 edges

Intuition. A spanning tree has exactly V - 1 edges and no cycle. The converse also holds: any V - 1 edges without a cycle connect all V vertices, because each such edge merges two separate pieces, and V - 1 merges turn V single-vertex pieces into one. So we can enumerate every subset of exactly V - 1 edges with a bitmask, check that it has no cycle, and keep the cheapest one.

To detect a cycle, give every vertex a piece label. An edge whose two ends already carry the same label closes a cycle; otherwise relabel one piece to merge the two.

Algorithm.

1. For every bitmask over the E edges with exactly V - 1 bits set:
2. Reset the labels, then add the chosen edges one by one, stopping at the first edge that closes a cycle.
3. If all V - 1 edges were added, the subset is a spanning tree; update the best weight.
4. Return the best weight, or -1 if no subset qualified.

static int bruteForce(int V, int[][] edges) {
    int E = edges.length, best = Integer.MAX_VALUE;
    for (int mask = 0; mask < (1 << E); mask++) {
        if (Integer.bitCount(mask) != V - 1) continue;
        int[] comp = new int[V];                           // comp[x]: label of the piece containing x
        for (int i = 0; i < V; i++) comp[i] = i;
        int weight = 0, merges = 0;
        for (int i = 0; i < E; i++) {
            if ((mask >> i & 1) == 0) continue;
            int a = comp[edges[i][0]], b = comp[edges[i][1]];
            if (a == b) break;                             // this subset contains a cycle
            for (int x = 0; x < V; x++) if (comp[x] == b) comp[x] = a;
            weight += edges[i][2];
            merges++;
        }
        if (merges == V - 1) best = Math.min(best, weight);    // V - 1 edges and no cycle: a spanning tree
    }
    return best == Integer.MAX_VALUE ? -1 : best;
}

Complexity. Time O(2^E · E · V): 2^E masks, each checked with up to E edges and an O(V) relabel. Space O(V). Only usable for about E ≤ 20. The real algorithms avoid enumeration by proving that a greedy choice is always safe.

Approach 2: Better, Prim’s algorithm with an array

Intuition. The key fact is the cut property. Split the vertices into any two non-empty groups S and the rest. The lightest edge crossing the split belongs to some minimum spanning tree. Proof by exchange: take an MST T that does not contain that lightest crossing edge e. Adding e to T creates a cycle. A cycle that crosses the split once must cross it again, so the cycle contains another crossing edge f. Since w(e) ≤ w(f), the tree T - f + e is still spanning and weighs no more than T. So it is also minimum, and it contains e.

Prim applies the cut property with S = the tree built so far. Start from vertex 0. At every step, attach the outside vertex reachable by the cheapest single edge from the tree. Keep key[v] = weight of the cheapest known edge between the tree and v. The structure looks like Dijkstra, but key[v] is a single edge weight, not a distance from the start.

Algorithm.

1. key[0] = 0, every other key ∞.
2. Repeat V times: scan for the outside vertex u with the smallest finite key. If none exists, the graph is disconnected: return -1.
3. Add u to the tree and add key[u] to the total. For every edge u - v with v outside, set key[v] = min(key[v], w).

static int better(int V, int[][] edges) {
    List<List<int[]>> adj = buildAdj(V, edges);
    int[] key = new int[V];                                // key[v]: cheapest known edge joining v to the tree
    Arrays.fill(key, Integer.MAX_VALUE);
    boolean[] inTree = new boolean[V];
    key[0] = 0;
    int total = 0;
    for (int iter = 0; iter < V; iter++) {
        int u = -1;
        for (int v = 0; v < V; v++) {
            if (!inTree[v] && key[v] != Integer.MAX_VALUE && (u == -1 || key[v] < key[u])) u = v;
        }
        if (u == -1) return -1;                            // some vertex can never be attached
        inTree[u] = true;
        total += key[u];
        for (int[] e : adj.get(u)) {
            if (!inTree[e[0]] && e[1] < key[e[0]]) key[e[0]] = e[1];
        }
    }
    return total;
}

Complexity. Time O(V^2 + E): V scans of O(V), plus each edge examined from both ends. Space O(V + E). On a dense graph (E ≈ V^2) this is optimal, since just reading the edges costs that much.

Approach 3: Optimal, Prim’s algorithm with a priority queue

Intuition. For sparse graphs the linear scan dominates. Keep candidate edges in a min-heap of {weight, vertex} instead. When a vertex joins the tree, push every edge from it to a vertex still outside. When we pop an entry whose vertex is already in the tree, that vertex was attached earlier through a cheaper edge, so the entry is stale and we skip it. At any moment the heap contains every edge leaving the tree (plus stale ones), so the first valid pop is the lightest edge crossing the cut, exactly what the cut property allows us to take.

Algorithm.

1. Push {0, 0} (vertex 0 joins at cost 0).
2. Pop {w, u}. If u is in the tree, skip it. Otherwise add it, add w to the total, and push {w', v} for each edge to an outside vertex v.
3. When the heap is empty, return the total if all V vertices joined, else -1.

static int optimal(int V, int[][] edges) {
    List<List<int[]>> adj = buildAdj(V, edges);
    boolean[] inTree = new boolean[V];
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));   // {edgeWeight, vertex}
    pq.add(new int[]{0, 0});
    int total = 0, added = 0;
    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int w = top[0], u = top[1];
        if (inTree[u]) continue;                           // u already joined through a cheaper edge
        inTree[u] = true;
        total += w;
        added++;
        for (int[] e : adj.get(u)) {
            if (!inTree[e[0]]) pq.add(new int[]{e[1], e[0]});
        }
    }
    return added == V ? total : -1;
}

Dry run on Example 2:

Complexity. Each edge is pushed at most once (when the first of its two ends joins the tree), so the heap holds O(E) entries and every operation costs O(log E) = O(log V). Time O(E log V), space O(V + E).

Recovering the tree. Many versions ask for the MST edges as well. Store the parent in each heap entry; when a vertex is accepted, {parent, vertex, weight} is a tree edge.

static List<int[]> optimalEdges(int V, int[][] edges) {
    List<List<int[]>> adj = buildAdj(V, edges);
    boolean[] inTree = new boolean[V];
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));   // {edgeWeight, vertex, parent}
    pq.add(new int[]{0, 0, -1});
    List<int[]> tree = new ArrayList<>();
    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int u = top[1];
        if (inTree[u]) continue;
        inTree[u] = true;
        if (top[2] != -1) tree.add(new int[]{top[2], u, top[0]});
        for (int[] e : adj.get(u)) {
            if (!inTree[e[0]]) pq.add(new int[]{e[1], e[0], u});
        }
    }
    return tree;
}

Edge cases and pitfalls

• Disconnected graph. There is no spanning tree. The array version notices that no outside vertex has a finite key; the heap version notices that fewer than V vertices joined.
• Single vertex. The MST is empty and weighs 0.
• Parallel edges and self loops. The heap simply holds both parallel edges and the cheaper one wins. A self loop never leads to an outside vertex, so it is never used.
• Negative weights. Unlike Dijkstra, Prim is fine with them: the cut property only compares weights, never sums them along a path. The tests include a negative edge.
• Ties. Several different MSTs can exist when weights repeat, but they all have the same total weight.
• Confusing Prim with Dijkstra. Pushing dist[u] + w instead of w builds a shortest-path tree, which is generally not an MST.
• Overflow. The total is at most (V - 1) · maxWeight; switch to long for large weights.

Related problems

• Prim’s Algorithm is the A2Z sheet’s version of the same algorithm.
• MST theory covers spanning trees and the cut property in more depth.
• MST using Kruskal’s Algo builds the same tree by sorting edges and using a disjoint set.
• Find the MST weight is the A2Z problem that asks for exactly this total.
• Dijkstra’s algorithm uses the same heap loop with a different key.