Prim’s algorithm builds a minimum spanning tree by growing a single tree and always adding the cheapest edge that reaches a new node. Choose a start node in the visualization below and watch the tree grow one edge at a time.
Operation log
Cut edges
Complexity (theory): O(V²) with an array, O((V + E) log V) with a binary heap. Works on connected, undirected, weighted graphs. The counters above are measured for the graph shown.
What Is Prim’s Algorithm?
Prim’s algorithm finds a minimum spanning tree (MST) of a connected, undirected, weighted graph. A spanning tree connects all nodes using exactly V − 1 edges and no cycles. The minimum spanning tree is the one whose total edge weight is as small as possible.
Prim’s algorithm is greedy. It starts from any node and grows one tree. At each step, it looks at every edge that connects a tree node to a node outside the tree, and it adds the cheapest one. This works because of the cut property: for any split of the nodes into two groups, the cheapest edge crossing the split belongs to some minimum spanning tree.
How Prim’s Algorithm Works: Steps, Example and Code
How Prim’s Algorithm Works Step by Step
- Pick any start node and add it to the tree.
- Find all edges that connect a tree node to a node outside the tree.
- Choose the edge with the smallest weight.
- Add that edge and its new node to the tree.
- Repeat from step 2 until every node is in the tree.
In the visualization, dashed nodes are candidates next to the tree, and the amber edge is the cheapest crossing edge being chosen. Blue edges belong to the tree.
Prim’s Algorithm Example With a Step-by-Step Walkthrough
Use edges A–B 4, A–C 2, B–C 1, B–D 5, C–D 8, C–E 10, D–E 2, D–F 6 and E–F 3. Start at A.
- Tree {A}. Crossing edges: A–B 4, A–C 2. Add A–C (2).
- Tree {A, C}. Crossing edges: A–B 4, B–C 1, C–D 8, C–E 10. Add B–C (1).
- Tree {A, B, C}. Crossing edges: B–D 5, C–D 8, C–E 10. Add B–D (5).
- Tree {A, B, C, D}. Crossing edges: C–E 10, D–E 2, D–F 6. Add D–E (2).
- Tree {A, B, C, D, E}. Crossing edges: D–F 6, E–F 3. Add E–F (3).
The minimum spanning tree has edges A–C, B–C, B–D, D–E and E–F, with total weight 2 + 1 + 5 + 2 + 3 = 13. Notice that Prim’s algorithm never added A–B (4), because B was reached more cheaply through C.
Prim’s Algorithm Pseudocode
Prim(graph, start):
inTree = { start }
mstEdges = [ ]
while inTree does not contain every node:
best = none
for each edge (u, v, w) with u in inTree and v not in inTree:
if best is none or w < best.w: best = (u, v, w)
if best is none: break // graph is disconnected
add best.v to inTree
add best to mstEdges
return mstEdgesThis version scans all crossing edges each round. A priority queue keyed by the cheapest known connection for each outside node makes it faster.
Prim’s Algorithm Implementation in JavaScript
function prim(graph, start) {
// graph: { A: [['B', 4], ['C', 2]], ... } (neighbor, weight), undirected
const inTree = new Set([start]);
const edges = [];
let total = 0;
const nodeCount = Object.keys(graph).length;
while (inTree.size < nodeCount) {
let best = null;
for (const u of inTree) {
for (const [v, w] of graph[u]) {
if (!inTree.has(v) && (best === null || w < best.w)) best = { u, v, w };
}
}
if (best === null) break; // disconnected graph: stop
inTree.add(best.v);
edges.push([best.u, best.v, best.w]);
total += best.w;
}
return { edges, total };
}Each outer round adds one node. If the graph is disconnected, the function stops and returns a minimum spanning forest for the start node’s component only.
Prim’s Algorithm Time and Space Complexity
Time Complexity of Prim’s Algorithm
| Implementation | Time | Notes |
|---|---|---|
| Adjacency matrix with array scan | O(V²) | Good for dense graphs |
| Binary heap and adjacency list | O((V + E) log V) | Good for sparse graphs |
| Fibonacci heap | O(E + V log V) | Best known bound, rarely used in practice |
Space Complexity of Prim’s Algorithm
Prim’s algorithm stores the set of tree nodes, the chosen edges, and, in the heap version, a key for every outside node. This is O(V) extra space beyond the graph.
Prim’s Algorithm Advantages, Disadvantages and Comparisons
Advantages and Disadvantages of Prim’s Algorithm
Advantages: it is simple, it grows a connected tree at every step, and it is fast on dense graphs with the array version.
Disadvantages: it needs a connected graph for a full spanning tree, it applies to undirected graphs, and it needs a heap or similar structure to be fast on sparse graphs. When edge weights tie, more than one MST can exist.
Prim’s Algorithm vs Kruskal’s Algorithm
| Feature | Prim | Kruskal |
|---|---|---|
| Strategy | Grow one tree from a node | Add the cheapest edge anywhere that avoids a cycle |
| Key structure | Priority queue | Sorted edges and union-find |
| Best for | Dense graphs | Sparse graphs |
| Intermediate result | Always one connected tree | A forest of several trees |
Using Prim’s Algorithm in Practice: Applications and Mistakes
Common Applications of Prim’s Algorithm
- Designing low-cost networks, such as cables, pipes or roads.
- Clustering, where long MST edges can be cut to form groups.
- Approximation algorithms, such as a 2-approximation for the metric traveling salesman problem.
- Image segmentation and other graph-based analysis.
Common Mistakes When Implementing Prim’s Algorithm
- Running it on a directed graph and expecting a spanning tree.
- Adding an edge whose two endpoints are both in the tree, which creates a cycle.
- Ignoring disconnected graphs, which have no spanning tree.
- Confusing a minimum spanning tree with a shortest-path tree: the MST minimizes total weight, not the distance from the start.
- Mixing up the total weight of the tree with the weight of a single edge.
Prim’s Algorithm Variations and Tips
A few extensions make Prim’s algorithm easier to use on real data.
Heap-Based Prim With Lazy Deletion
Keep a min-heap of candidate edges. Start by pushing the edges of the start node. Each time you pop an edge, skip it if its far end is already in the tree, and otherwise add that node and push its edges. This gives O((V + E) log V) time and is simple to code.
Maximum Spanning Tree
To find a spanning tree with the largest total weight, pick the heaviest crossing edge each time, or negate all weights and run the normal algorithm.
Disconnected Graphs
A disconnected graph has no spanning tree, but it has a minimum spanning forest. Run Prim’s algorithm from every node that is not yet in a tree, and combine the results.
A Practical Example: Connecting Offices
Imagine a company that wants to link six offices with network cable, where each possible link has a known cost. The offices are the nodes, the possible cables are the edges, and the cost is the weight. A minimum spanning tree gives the cheapest set of cables that still connects every office. Prim’s algorithm builds it by starting at the head office and repeatedly adding the cheapest cable that reaches an office not yet connected. The result has exactly five cables, no loops, and the lowest possible total cost. Note that the tree minimizes total cost, not the distance between any two offices, so for fastest routes between offices you would use a shortest-path algorithm instead.
When the MST Is Unique
If all edge weights are distinct, the minimum spanning tree is unique. When some weights tie, several trees can have the same minimum total weight, and different start nodes or tie-breaking rules can produce different, equally valid trees.
Testing Prim’s Algorithm
There are simple ways to confirm that your tree is correct.
Compare With Kruskal’s Algorithm
Run Kruskal’s algorithm on the same graph. The total weight must match Prim’s total exactly, even if the chosen edges differ because of ties.
Check the Tree Properties
- The tree must contain exactly V − 1 edges.
- Every node must be connected to the tree.
- There must be no cycle.
- Removing any tree edge must disconnect the tree.
Edge Cases to Try
- A graph with one node, which has an empty tree.
- A graph with two nodes, which has one edge.
- A graph where all weights are equal, where any spanning tree is minimal.
- A disconnected graph, which should report a forest or an error.
Frequently Asked Questions About Prim’s Algorithm
What is Prim’s algorithm in simple words?
It grows a tree from one node by repeatedly adding the cheapest edge that reaches a new node.
What is a minimum spanning tree?
A set of V − 1 edges that connects all nodes with the smallest possible total weight.
Is Prim’s algorithm greedy?
Yes. It always picks the cheapest crossing edge.
What is the time complexity of Prim’s algorithm?
O(V²) with an array, and O((V + E) log V) with a binary heap.
Does the start node change the result?
The total MST weight stays the same. The set of edges can differ only when several MSTs exist because of ties.
Prim or Kruskal?
Prim often suits dense graphs and Kruskal often suits sparse graphs. Both give an MST.
Does Prim’s algorithm work with negative weights?
Yes. Unlike Dijkstra’s algorithm, it only compares edge weights, so negative weights are allowed.
Conclusion
Prim’s algorithm builds a minimum spanning tree by repeatedly adding the cheapest edge between the tree and the rest of the graph. It is simple, greedy and correct because of the cut property. Try different start nodes and new random weights in the visualization and watch the tree grow.