☕ DSA Java Articles

Topics › Graphs › MinimumSpanningTree/Disjoint Set and Problems

Prim's Algorithm

Hard TUF ID 2825 A2Z

Java source ↗ Edit this article ↗

Problem

Given a connected, undirected, weighted graph with V vertices numbered 0 to V - 1 and a list of edges [u, v, w], return the total weight of a minimum spanning tree: a set of V - 1 edges that connects every vertex with the smallest possible total weight. Also list the edges of that tree. (GeeksforGeeks passes the graph as an adjacency list; an edge list carries the same information and is easier to write in tests.) If the graph turns out to be disconnected, no spanning tree exists and the Java methods return -1.

Constraints (GeeksforGeeks “Minimum Spanning Tree”): 2 ≤ V ≤ 1000, V - 1 ≤ E ≤ V(V-1)/2, 1 ≤ w ≤ 1000, no self-loops or parallel edges.

Example 1

V = 3, edges = [[0,1,5], [1,2,3], [0,2,1]]
answer = 4          // edges 0-2 (1) and 1-2 (3)

Example 2

V = 5, edges = [[0,1,2], [0,2,1], [1,2,1], [2,3,2], [3,4,1], [4,2,2]]
answer = 5          // 0-2 (1), 2-1 (1), 2-3 (2) or 2-4 (2), 3-4 (1)

The idea behind Prim’s algorithm

Prim’s algorithm grows a single tree outward from a start vertex. At every step the tree covers some set S of vertices, and the algorithm adds the cheapest edge that leaves S, together with the new vertex at its far end. After V - 1 additions, every vertex is in the tree.

Why is the greedy choice safe? It is the cut property: for the cut (S, everything else), the lightest crossing edge belongs to some minimum spanning tree. Suppose the edges chosen so far are part of some MST T, but T does not use the newly chosen edge e = (u, v) with u in S. The path in T from u to v must leave S through some edge f, and w(f) ≥ w(e) because e was the cheapest edge leaving S. Replacing f by e gives a spanning tree that is no heavier and contains everything chosen so far. By induction, the final tree is an MST.

The two approaches below differ only in how they find “the cheapest edge leaving S”.

Approach 1: Array-based Prim, O(V²)

Intuition. Maintain key[v], the weight of the cheapest edge from the current tree to each outside vertex v, and parent[v], the tree vertex at the other end of that edge. Each step scans all outside vertices for the smallest key, adds that vertex, and then updates the keys of its neighbours, since the new vertex may offer cheaper connections. With an adjacency matrix the update is one pass over a row.

Algorithm.

  1. Build a weight matrix, keeping the lighter of any parallel edges. Set key[0] = 0 and every other key to infinity.
  2. Repeat V times: pick the outside vertex u with the smallest key. If that key is infinite, the graph is disconnected, so return -1.
  3. Add u to the tree, add key[u] to the total, and record the edge parent[u] - u.
  4. For every outside v, if w[u][v] < key[v], set key[v] = w[u][v] and parent[v] = u.
static int primArray(int n, int[][] edges, List<int[]> mstEdges) {
    int[][] w = new int[n][n];
    for (int[] row : w) Arrays.fill(row, INF);
    for (int[] e : edges) {                          // keep the cheapest of parallel edges
        w[e[0]][e[1]] = Math.min(w[e[0]][e[1]], e[2]);
        w[e[1]][e[0]] = Math.min(w[e[1]][e[0]], e[2]);
    }
    int[] key = new int[n], parent = new int[n];     // key[v] = cheapest edge from the tree to v
    boolean[] inTree = new boolean[n];
    Arrays.fill(key, INF);
    Arrays.fill(parent, -1);
    key[0] = 0;
    int total = 0;
    for (int step = 0; step < n; step++) {
        int u = -1;
        for (int v = 0; v < n; v++) if (!inTree[v] && (u == -1 || key[v] < key[u])) u = v;
        if (key[u] == INF) return -1;                // nothing outside the tree is reachable
        inTree[u] = true;
        total += key[u];
        if (parent[u] != -1) mstEdges.add(new int[]{parent[u], u, key[u]});
        for (int v = 0; v < n; v++) {
            if (!inTree[v] && w[u][v] < key[v]) {
                key[v] = w[u][v];
                parent[v] = u;
            }
        }
    }
    return total;
}

Complexity. Time O(V²): V steps, each scanning V keys and one matrix row. Space O(V²) for the matrix. On dense graphs, where E is close to V², this is optimal, because just reading the edges takes that long. On sparse graphs it wastes time scanning vertices that have no nearby edges.

Approach 2: Lazy Prim with a min-heap, O(E log E)

Intuition. Instead of scanning for the minimum key, keep candidate edges in a min-heap ordered by weight. Each entry is {weight, node, parent}: “you can attach node to the tree through parent at this cost”. When a vertex joins the tree, push one entry for each of its edges to outside vertices. When an entry is popped, the vertex may already have joined through a cheaper edge. In that case the entry is outdated and is ignored. This is the lazy version: we never delete or decrease entries, we just skip the stale ones.

Popping the smallest entry whose node is outside the tree is exactly “the cheapest edge leaving S”. Every edge from S to the outside was pushed when its tree endpoint joined, and every entry pointing into S is skipped.

Algorithm.

  1. Build an adjacency list. Push {0, 0, -1}: vertex 0 joins at cost 0 with no parent.
  2. Pop the lightest entry {wt, u, parent}. If u is already in the tree, skip it.
  3. Otherwise mark u, add wt to the total, record edge parent - u (unless parent is -1), and push {w, v, u} for every neighbour v not yet in the tree.
  4. When the heap is empty, return the total if all V vertices joined, else -1.
static int primHeap(int n, int[][] edges, List<int[]> mstEdges) {
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i < n; 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]});
    }
    boolean[] inTree = new boolean[n];
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    pq.offer(new int[]{0, 0, -1});                   // start anywhere: vertex 0 with no parent
    int total = 0, added = 0;
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int wt = cur[0], u = cur[1], parent = cur[2];
        if (inTree[u]) continue;                     // a cheaper edge already pulled u in
        inTree[u] = true;
        total += wt;
        added++;
        if (parent != -1) mstEdges.add(new int[]{parent, u, wt});
        for (int[] e : adj.get(u)) {
            if (!inTree[e[0]]) pq.offer(new int[]{e[1], e[0], u});
        }
    }
    return added == n ? total : -1;
}

Dry run on Example 1 (0-1 (5), 1-2 (3), 0-2 (1)):

pop in tree already? action heap after
{0, 0, -1} no total = 0; push {5,1,0}, {1,2,0} {1,2,0}, {5,1,0}
{1, 2, 0} no total = 1, edge 0-2; push {3,1,2} {3,1,2}, {5,1,0}
{3, 1, 2} no total = 4, edge 2-1 {5,1,0}
{5, 1, 0} yes skip empty

The total is 4, with edges 0-2 and 2-1.

Complexity. Time O(E log E): each undirected edge is pushed at most twice (once from each endpoint), and each push or pop costs O(log E). Since E ≤ V², log E ≤ 2 log V, so this is also written O(E log V). Space O(V + E) for the adjacency list and the heap.

An eager variant keeps at most one heap entry per vertex and decreases its key in place (an indexed heap), which bounds the heap at V entries. Java’s PriorityQueue has no decrease-key operation, so the lazy version is the usual choice in Java.

Choosing between the two

For sparse graphs (E around V), the heap version’s O(E log E) is far below O(V²). For dense graphs the array version avoids the heap’s overhead and log factor. Kruskal’s algorithm, which sorts all edges and uses a disjoint-set structure, is the other standard option. It is usually simpler when the input is already an edge list.

Edge cases and pitfalls