Prim MST Visualization for Coding Interviews

By Rahul Kumar · Senior Software Engineer · Updated May 2026 · Category: Graphs

Grow tree from a seed vertex; min-heap over fringe edges.

Concept

Prim's algorithm grows a minimum spanning tree one vertex at a time, always extending the tree along the lightest edge that crosses from the in-tree set to the outside. Unlike Kruskal's edge-centric view, Prim's is vertex-centric and feels structurally similar to Dijkstra's shortest-path algorithm: both pop the closest unfinished vertex from a priority queue and relax its neighbors. The key difference is that Prim's key for a vertex is the weight of the cheapest edge connecting it to the current tree (not the distance from a source). On dense graphs represented as adjacency matrices, Prim's can run in O(V^2) with a plain array. On sparse graphs with adjacency lists and a binary heap, it runs in O(E log V). Fibonacci heaps bring it down to O(E + V log V) in theory but are rarely faster in practice. Prim's is preferred when edges are not pre-materialized, when memory for a full edge list would be prohibitive, or when you already have an adjacency-list graph in hand.

Prim MST — Interactive Simulator

Runs fully client-side in your browser; no sign-up. Or open full screen →

Launch the interactive Prim MST visualization — animated algorithm, step-through, and live data-structure updates.

How it works

We start at any vertex and maintain a min-priority queue of candidate fringe edges (weight, neighbor, from). We also maintain a boolean inTree[] array marking which vertices have already been absorbed into the MST. To begin we push every edge incident to the start vertex and mark the start as in-tree. Each main iteration pops the lightest fringe edge. If its neighbor is already in the tree we discard it (this is lazy deletion to avoid decrease-key). Otherwise we add the edge to the MST, mark the neighbor as in-tree, and push all of the neighbor's outgoing edges whose other endpoint is not yet in the tree. We stop when either the MST contains V-1 edges or the queue empties. Correctness again follows from the cut property: the cut between in-tree and out-of-tree vertices changes each iteration, and the lightest crossing edge is always safe to add. The lazy-deletion style keeps code small and uses only a single PriorityQueue, trading O(E) extra heap entries for simplicity. An eager variant uses a key[] array and decrease-key operations to keep the heap at size V.

Implementation

Prim's MST with a lazy min-heap

import java.util.*;

public class Prim {
    public static class Result {
        public final List<int[]> edges; // {u, v, w}
        public final long totalWeight;
        public Result(List<int[]> edges, long totalWeight) {
            this.edges = edges;
            this.totalWeight = totalWeight;
        }
    }

    /**
     * adj.get(u) contains int[]{neighbor, weight} entries.
     * Returns the MST edges and total weight. Assumes connected graph.
     */
    public static Result primMST(List<List<int[]>> adj, int n) {
        boolean[] inTree = new boolean[n];
        // entry: {weight, to, from}
        PriorityQueue<int[]> pq =
            new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

        inTree[0] = true;
        for (int[] nbr : adj.get(0)) {
            pq.offer(new int[]{nbr[1], nbr[0], 0});
        }

        List<int[]> picked = new ArrayList<>();
        long total = 0;
        while (!pq.isEmpty() && picked.size() < n - 1) {
            int[] top = pq.poll();
            int w = top[0], to = top[1], from = top[2];
            if (inTree[to]) continue;
            inTree[to] = true;
            picked.add(new int[]{from, to, w});
            total += w;
            for (int[] nbr : adj.get(to)) {
                if (!inTree[nbr[0]]) {
                    pq.offer(new int[]{nbr[1], nbr[0], to});
                }
            }
        }
        return new Result(picked, total);
    }

    public static void main(String[] args) {
        int n = 4;
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int[][] edges = {{0,1,1},{0,2,4},{1,2,2},{1,3,5},{2,3,3}};
        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]});
        }
        Result r = primMST(adj, n);
        System.out.println("weight=" + r.totalWeight);
    }
}

Complexity

Time: O(E log V)
Space: O(V+E)

Common pitfalls

Forgetting the inTree check after polling, which would add duplicate edges and corrupt the MST.
Using an int accumulator for total weight; large MSTs easily overflow, so prefer long.
Pushing both directions of an undirected edge into the heap without tracking from-vertices, producing bogus MST edges.
Seeding from a disconnected component, which silently returns an incomplete MST without signaling the disconnect.

Key design decisions & trade-offs

Lazy vs eager heap — Chosen: Lazy PriorityQueue with duplicates. Java's PriorityQueue has no decrease-key; lazy deletion keeps the code short and is competitive in practice.
Prim vs Kruskal — Chosen: Prim when starting from adjacency lists. Avoids materializing and sorting the full edge list; natural when graph is discovered incrementally.

Practice problems

Min Cost to Connect All Points

Interview follow-ups

Detect disconnected graphs by checking picked.size() at the end and reporting the unreachable set.
Implement an eager version with an indexed priority queue (heap plus position map) to shave log factors.
Adapt to Steiner tree approximations by restricting the starting set to terminal vertices.

Why it matters

Prim MST is a core part of the Graphs toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".