Graph Algorithms

Prim's Algorithm

What is Prim's Algorithm?

Prim's algorithm builds a minimum spanning tree the same way Kruskal's does — greedily, ending up with the cheapest possible set of edges connecting every vertex with no cycles — but it grows outward from a single starting vertex instead of considering edges from the whole graph in sorted order. At every step, the tree adds whichever edge is cheapest among all the edges connecting the current tree to a vertex not yet in it.

How Does It Work?

Rather than sorting the whole edge list up front, Prim's algorithm tracks a "key" value for every vertex outside the tree: the weight of the cheapest edge discovered so far connecting it directly to the tree (infinity if none is known yet). At each step, the algorithm pulls in whichever outside vertex has the smallest key, adds the edge that earned it that key, and then checks whether any of its edges give some other outside vertex an even cheaper way into the (now larger) tree.

This "key" is deliberately different from Dijkstra's "distance": Dijkstra's distance is the cumulative weight of the entire path from the start, while Prim's key is just the weight of one direct edge into the tree, regardless of how far the tree has traveled to get there. That's exactly why Prim's algorithm finds a minimum spanning tree — cheapest total connections — while Dijkstra finds shortest paths — cheapest cumulative routes. They look almost identical in code, but they're solving genuinely different problems.

Starting from A, the tree grows one cheapest-edge step at a time

Algorithm Steps

Set the start vertex's key to 0, and every other vertex's key to infinity
While vertices remain outside the tree, repeat:
- Pull in whichever outside vertex currently has the smallest key, and add the edge that produced that key to the tree
- For each of its edges to a still-outside vertex, if that edge is cheaper than the outside vertex's current key, update the key
Once every reachable vertex is in the tree, the accepted edges form the minimum spanning tree

Time Complexity

Time Complexity: O((V + E) log V) with a binary heap priority queue — comparable to Dijkstra's, and often faster than Kruskal's on dense graphs.
Space Complexity: O(V) — for the key array, the parent pointers, and the priority queue.

Time Complexity Analysis

Prim's algorithm tends to be the better choice on dense graphs (many edges relative to vertices), since it never needs to sort the full edge list the way Kruskal's does — with a good priority queue it can outperform Kruskal's as edge count grows. Like Kruskal's, it's used for minimum-cost network design: wiring, piping, or cabling a set of locations together as cheaply as possible.

Daily DSA Challenge by Scale Engineer

Grow a minimum spanning tree outward, always pulling in the cheapest edge that reaches a new vertex

Build a weighted graph, pick a start vertex, and run Prim's algorithm

Graph

Add a vertex to begin

Outside the treeIn the treeJust pulled in / key updated

Test Your Knowledge before moving forward!

Prim's Algorithm Quiz

How it works:

+1 point for each correct answer
0 points for wrong answers
-0.5 point penalty for viewing explanations
Earn stars based on your final score (max 5 stars)

Prim's Algorithm Implementation

// "key" is the weight of the cheapest edge discovered so far connecting a
// vertex directly to the tree -- not a cumulative distance like Dijkstra's.
function prim(vertices, adjList, start) {
  const key = {};
  const parent = {};
  const inTree = new Set();
  vertices.forEach((v) => (key[v] = Infinity));
  key[start] = 0;

  while (inTree.size < vertices.length) {
    // Pick the outside vertex with the smallest key
    let u = null;
    let best = Infinity;
    for (const v of vertices) {
      if (!inTree.has(v) && key[v] < best) {
        best = key[v];
        u = v;
      }
    }
    if (u === null) break; // remaining vertices are unreachable

    inTree.add(u);

    for (const { to, weight } of adjList[u] || []) {
      if (!inTree.has(to) && weight < key[to]) {
        key[to] = weight; // a cheaper direct connection was just found
        parent[to] = u;
      }
    }
  }

  const mstEdges = [];
  vertices.forEach((v) => {
    if (parent[v] !== undefined) mstEdges.push({ from: parent[v], to: v, weight: key[v] });
  });
  return mstEdges;
}

// Usage example
const adjList = {
  A: [{ to: "B", weight: 4 }, { to: "C", weight: 1 }],
  B: [{ to: "A", weight: 4 }, { to: "C", weight: 2 }, { to: "D", weight: 5 }],
  C: [{ to: "A", weight: 1 }, { to: "B", weight: 2 }, { to: "D", weight: 8 }],
  D: [{ to: "B", weight: 5 }, { to: "C", weight: 8 }],
};
prim(["A", "B", "C", "D"], adjList, "A"); // A-C, C-B, B-D

Done With the Learning

Mark Prim's Algorithm as done and view it on your dashboard

Explore Other Topics

Kruskal's Algorithm

Topological Sort

Dijkstra's Algorithm

Breadth-First Search

Depth-First Search