Prim Algorithm

Prim's algorithm finds the Minimum Spanning Tree (MST) of a weighted graph. The MST connects all vertices with the minimum total edge weight — no cycles.

Same problem as Kruskal's, different strategy.

The intuition

Start at any vertex. Look at all edges leaving the current tree. Pick the cheapest one that connects to a vertex not yet in the tree. Add it. Repeat until every vertex is included.

Think of it like growing a plant. You start at one root and always extend the cheapest branch to reach a new node.

The code

function primMST(graph) {
    const vertices = Object.keys(graph);
    const visited = new Set();
    const mst = [];
    let totalWeight = 0;

    visited.add(vertices[0]);

    while (visited.size < vertices.length) {
        let minEdge = null;
        let minWeight = Infinity;

        for (const vertex of visited) {
            for (const [neighbor, weight] of Object.entries(graph[vertex])) {
                if (!visited.has(neighbor) && weight < minWeight) {
                    minWeight = weight;
                    minEdge = { from: vertex, to: neighbor, weight };
                }
            }
        }

        if (minEdge) {
            visited.add(minEdge.to);
            mst.push(minEdge);
            totalWeight += minEdge.weight;
        }
    }

    return { mst, totalWeight };
}

Complexity

• Time: O(V^2) for the simple version above. With a binary heap (priority queue), it's O(E log V). With a Fibonacci heap, O(E + V log V).
• Space: O(V) for the visited set and MST edges.

Prim vs Kruskal

Prim grows the tree from a single vertex. Works well on dense graphs. Naturally fits an adjacency list.

Kruskal sorts all edges globally and adds them one by one. Works well on sparse graphs. Needs a Union-Find structure.

Both produce the same MST (assuming unique edge weights). The choice depends on your graph's density and representation.

Trade-offs

The simple O(V^2) version is fine for small or dense graphs. For large sparse graphs, you need a priority queue to avoid scanning all edges from visited vertices. The priority queue version is more code but dramatically faster on real-world graphs.