Prim's Algorithm

How It Works

Prim's algorithm grows a minimum spanning tree outward from an arbitrary start node. Maintain a min-heap of candidate edges that cross from the tree to the rest of the graph. Repeatedly pop the cheapest crossing edge; if its far endpoint is not yet in the tree, add the node and the edge, then push all of that node's edges to non-tree neighbors. The cut property guarantees each cheapest crossing edge belongs to some MST, so V−1 accepted edges form an optimal tree.

With a binary heap and adjacency list the runtime is O(E log V) — every edge is pushed at most once and each heap operation costs O(log V). The structure mirrors Dijkstra almost line for line; the only difference is the heap key, which is the single edge weight rather than the accumulated path distance from the source.

Step-by-Step Visualization

Code

static int prim(List<int[]>[] graph, int n) {
  boolean[] visited = new boolean[n];
  PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
  pq.add(new int[]{0, 0}); // [weight, node]
  int mstWeight = 0, count = 0;

  while (count < n) {
    int[] curr = pq.poll();
    int w = curr[0], u = curr[1];
    if (visited[u]) continue;
    visited[u] = true;
    mstWeight += w;
    count++;

    for (int[] edge : graph[u])
      if (!visited[edge[0]]) pq.add(new int[]{edge[1], edge[0]});
  }
  return mstWeight;
}

Tips & Gotchas

Practice Problems

• 1Min Cost to Connect All Points
• 2Optimize Water Distribution in a Village
• 3Minimum Cost to Connect Sticks

About the Minimum Spanning Tree Pattern

Connect all nodes in an undirected weighted graph with minimum total edge weight, using exactly V−1 edges (no cycles). Two classic algorithms: sort edges and add greedily (Kruskal's), or grow a tree from a node (Prim's).

Common Graphs Interview Problems

• Number of Islands
• Clone Graph
• Course Schedule
• Pacific Atlantic Water Flow
• Network Delay Time
• Minimum Spanning Tree
• Word Ladder

Frequently Asked Questions

Other Minimum Spanning Tree Techniques