Motivation
A minimum spanning tree connects every vertex of an undirected weighted graph with minimum total edge weight. Kruskal's algorithm grows a forest by choosing edges globally. Prim's algorithm instead grows one connected tree from a chosen root, repeatedly attaching the cheapest edge crossing from the tree to an unvisited vertex. Its correctness follows from a cut exchange argument, while an efficient implementation maintains the cheapest known connection for each outside vertex.
Edge weights may be negative or tied. Unlike a shortest-path algorithm, Prim's key is the weight of one crossing edge, not the length of a path from the root. The distinction matters even though both algorithms can use a priority queue.
Definitions
Definition 3.7.1
(Spanning tree and cut)
Let be a finite connected undirected graph with and real edge weights. A spanning tree is a connected acyclic set of edges containing every vertex. For a nonempty proper subset , an edge crosses the cut if one endpoint is in and the other outside it.
Definition 3.7.2
(Prim's algorithm)
Prim's algorithm starts with a root in and no chosen edges. While , choose a minimum-weight edge crossing , add that edge, and add its outside endpoint to . Ties may be broken arbitrarily. In a connected graph such an edge exists whenever is nonempty and not all of .
Theorems
Theorem 3.7.3
(Prim's algorithm is correct)
For every connected weighted undirected graph, Prim's algorithm terminates with a minimum spanning tree, including when weights are negative or tied.
Theorem 3.7.4
(Indexed binary-heap implementation)
With adjacency lists and an indexed binary min-heap supporting extract-min and decrease-key in time, Prim's algorithm runs in time and space for .
Proof sketch or proof idea
Proof
(Prim's invariant gives a minimum spanning tree)
Maintain the invariant that the chosen edges form a tree on and are contained in some minimum spanning tree . Initially the chosen set is empty, so the invariant holds. Let be a minimum edge crossing the current cut. If , the same minimum tree witnesses the invariant after adding . Otherwise, adding to creates a unique cycle. The path between 's endpoints crosses the cut, so the cycle contains another crossing edge . The chosen edges lie entirely within , hence is not one of them. Since , replacing by gives a spanning tree of weight no larger than . Minimality makes it another minimum spanning tree containing the enlarged chosen set.
Adding an edge to one new vertex preserves connectedness and acyclicity of the chosen subgraph. Each iteration increases by one, so after additions it is a spanning tree. The invariant says it is contained in a minimum spanning tree; both have edges, so they are equal. The proof uses only comparisons of edge weights and works with negative weights and equality.
Proof X-ray
A safe edge preserves an optimum
The exchange does not claim that the chosen edge belongs to every minimum tree. It builds one minimum tree that contains all earlier choices and the new edge. Three facts carry the argument. The tree path between the endpoints of must cross the cut, which provides a replacement edge whatever the weights are. Every chosen edge has both endpoints in , so is not a chosen edge and removing it keeps all earlier choices. Finally , because is lightest across the cut, so the swap cannot increase the weight. Only this one comparison involves weights, which is why negative and tied weights cause no difficulty. If were not lightest, the swap could increase the weight and the invariant would fail.
Proof
(Heap keys are lightest crossing edges)
For the heap implementation, maintain for each vertex outside a key equal to the lightest edge currently known from to that vertex, and a parent endpoint witnessing that key. The root has key zero initially and all other keys are infinity. When a vertex is extracted, scan its adjacency list and decrease a neighbor's key whenever the new crossing edge is lighter. Induction on extracted vertices shows that each finite key is the minimum weight among edges from the current to that outside vertex. Thus the minimum key gives a globally lightest crossing edge.
There are extractions and at most two adjacency-list inspections per undirected edge. At most successful key decreases occur. Each heap operation takes , while graph and heap storage is . A binary heap's height is ; extract-min and decrease-key restore heap order along at most one root-to-leaf path. Connectivity ensures every extracted non-root vertex has a finite witnessed key.
Worked examples
Worked example 3.7.5
(Growing a tree)
For a triangle with weights , and , start at . The lightest crossing edge is , then the lightest edge from to is . The result has weight .
Worked example 3.7.6
(A negative edge)
For a triangle with weights , Prim may choose the negative edge first. Its exchange proof still applies: minimum spanning trees minimize total weight, and no nonnegative-weight hypothesis was used.
Worked example 3.7.7
(Ties need not imply a unique tree)
In a triangle whose three edges all have weight one, any two edges form a minimum spanning tree. Different tie choices can return different trees, each of total weight two.
Common mistakes
Counterexample mode
A Prim key is not a path distance
In a path with edge weights and , after adding the Prim key of is , the weight of edge . The shortest-path distance from to is . Treating the key as a path distance confuses two different objectives.
Common mistake
(Connectivity and priority-queue updates)
Connectivity is needed for the single-tree algorithm as stated. On a disconnected graph the cut may have no crossing edge before all vertices are reached; restarting in each component gives a spanning forest but needs a separate output specification. A priority queue must support updates consistently with the current key; stale entries in another implementation need their own correctness and complexity analysis.
The cut exchange in detail
The invariant is existential: after each step there is at least one minimum spanning tree containing all chosen edges. A tie may mean that several minimum trees exist, and the newly chosen edge need not belong to all of them. The exchange argument is strong enough to preserve one suitable optimum without assuming uniqueness.
When an edge joins a vertex in to one outside, adding it to a spanning tree creates a unique cycle. This follows because a tree already has a unique path between the endpoints; the path plus is the cycle. That path begins inside and ends outside, so it contains at least one edge crossing the cut. Removing breaks the cycle and leaves a connected spanning tree. The already chosen edges have both endpoints in , so none can be this crossing edge. The replacement keeps every earlier choice.
If and have equal weights, the new tree has exactly the same weight. If were strictly lighter, the new tree would be lighter than the assumed minimum, which cannot happen; the inequality is still enough to establish a minimum tree containing . This reasoning applies even when some weights are negative. A spanning tree has a fixed number of edges and cannot repeat a negative edge, so the negative-cycle issue from shortest walks is not the relevant question here.
Worked example 3.7.8
(A minimum tree need not preserve shortest paths)
Take a triangle with , and . Prim starting at chooses and then , producing a minimum spanning tree of weight four. Its path from to has weight four, while the shortest path in the original graph is the direct edge of weight three. Minimum total tree weight and shortest distance from a root are different objectives.
Maintaining the heap invariant
Before the root is extracted, its key is zero and every other key is infinity. No edge is selected for the root. After extracting a vertex , add it to and scan its incident edges. For every neighbor still outside , compare the edge weight with 's current key. If it is smaller, update the key and record as its parent. An equal-weight edge need not replace the previous parent: the existing edge remains a valid crossing witness.
Assume before adding that every outside key is the minimum edge weight from the old to that vertex. The only new crossing candidates after adding are edges incident to . Scanning them and taking the minimum restores the invariant. The smallest key across all outside vertices is therefore the smallest weight of any crossing edge. Its parent edge is a legal Prim choice. This explains both why the heap produces the abstract algorithm and why merely extracting a minimum numerical label would be insufficient without the key invariant.
An indexed heap keeps at most one active heap entry per outside vertex and tracks its position so decrease-key can find it. On extract-min, replacing the root entry by the last entry and moving it downward restores heap order along a path of height . A decrease-key moves the changed entry upward along at most one such path. A build by inserting initial entries takes , within the stated bound; a linear-time heap build is possible but is not required for this analysis.
Every undirected edge appears in the adjacency lists of its two endpoints. It is inspected at most twice as vertices enter , so there are inspections and at most that many successful key decreases. With extractions, the heap operations take time for . The heap and per-vertex arrays use space, and the adjacency lists use . The case returns the empty edge set immediately.
Disconnected graphs and conventions
If the graph is disconnected, a cut separating the current component from all other components can have no crossing edge. A version designed to return a minimum spanning forest may restart Prim from an unvisited vertex whenever it finishes one component. Running the connected-graph proof independently on each component shows that the union is a minimum spanning forest, defined as a minimum spanning tree in every component. This is a different output specification from a single spanning tree.
Parallel edges are harmless if each is inspected and counted in ; the cheapest one may become the key witness. Self-loops never cross a cut and cannot belong to a spanning tree, so they can be ignored. If the input representation contains them, the adjacency scan must avoid treating one as an edge to an outside vertex. These conventions do not affect the exchange proof.
For a one-vertex connected graph, the empty edge set is its unique spanning tree and has total weight zero. For a disconnected graph with several isolated vertices, a spanning forest has one singleton component per vertex and no edges. Stating such edge cases prevents a heap implementation from attempting to add a parent edge for a root.
Comparing algorithm guarantees
Prim and Kruskal both use safe-edge arguments, but their current structures differ. Prim maintains one connected set and chooses across its cut; Kruskal maintains a forest and considers edges in global weight order, rejecting those that would create a cycle. Neither algorithm requires all weights to be distinct. Different tie choices can produce different minimum spanning trees, so comparing edge lists is not a sound correctness check when ties are present; compare total weights and verify the tree property or use a suitable certificate.
A minimum spanning tree optimizes the sum of its selected edges. It need not minimize the route from the root to each vertex, as the triangle example shows. Dijkstra's algorithm maintains tentative path lengths and has different hypotheses and invariants. Sharing a min-heap does not make the meanings of the two keys interchangeable.
Common mistake
(A valid spanning tree is not necessarily minimum)
A finite run can be checked for basic validity by confirming that it selects edges, has no cycle and connects all vertices. Those conditions prove it is a spanning tree, not that it is minimum. The exchange proof supplies optimality for Prim's choices. An independently supplied tree would need an additional minimum-tree certificate or comparison algorithm to establish optimality.
Certifying a proposed tree and its uniqueness
Suppose someone gives us a spanning tree without telling us how it was found. For each non-tree edge with distinct endpoints, let be the unique path in joining its endpoints. Adding creates a cycle consisting of this path and . A useful certificate is
This condition is necessary and sufficient for to be minimum. It also handles tied and negative weights; self-loops can be ignored because no spanning tree contains one. If there are no non-tree, non-loop edges, the condition is vacuous and is the only spanning tree.
Theorem 3.7.9
(Cycle certificate for minimum spanning trees)
A spanning tree is a minimum spanning tree if and only if for every non-tree, non-loop edge . It is the unique minimum spanning tree exactly when every such inequality is strict.
Proof
(Certificate characterizes minimum and unique trees)
For necessity, if some is lighter than a path edge , adding and removing gives a lighter spanning tree. For sufficiency, take any spanning tree . If , choose and remove it from , producing a cut. The path between the endpoints of crosses this cut; choose a crossing edge on that path. Since was the only edge of crossing the cut, , and the path between the endpoints of contains . The certificate gives . Replacing by in makes another spanning tree of no greater weight, with one more edge in common with . Repeat until reaching . Thus for every spanning tree .
The same argument identifies uniqueness: is the unique minimum spanning tree exactly when every comparison in the certificate is strict. If equality holds for a non-tree edge and a maximum-weight path edge , swapping them gives a different tree of the same weight. Conversely, if all comparisons are strict, the first replacement in the preceding argument strictly lowers the weight of every tree . Distinct edge weights are therefore sufficient for uniqueness, but they are not necessary.
Worked example 3.7.10
(Ties and an optimality certificate)
In a triangle, take and , and propose . Its only non-tree edge is ; the maximum weight on its tree path is , strictly less than . Hence is the unique minimum tree even though two edges have the same weight. If instead , equality permits swapping for either path edge, producing another minimum tree. If , the certificate fails and replacing by lowers the total weight from to .
The certificate assumes that has already been checked to be a spanning tree; path comparisons alone do not establish connectivity or acyclicity. Checking each path by a fresh tree traversal is a straightforward polynomial-time method. Faster path-maximum data structures require a separate analysis.
Summary
Prim grows a connected tree using a lightest edge across its current cut. An exchange argument maintains compatibility with a minimum spanning tree. An indexed heap maintains the cheapest crossing edge to each outside vertex and gives the stated adjacency-list complexity.
Exercises
Quick check
(How many edges does Prim add on a connected graph with vertices?)
Each added edge brings in one new vertex.
Solution · Answer
It adds edges, one for each vertex other than the root.
Quick check
(Does a negative edge invalidate the cut exchange proof?)
Which comparison between weights does the proof make?
Solution · Answer
No. The proof uses only that the chosen crossing edge is no heavier than the exchanged crossing edge.
Quick check
(What does a vertex's Prim key represent?)
Is it a path length or a single edge weight?
Solution · Answer
It is the smallest known weight of a single edge from the current tree to that outside vertex.
Quick check
(Why must a crossing edge exist before termination on a connected graph?)
What would a missing crossing edge say about paths?
Solution · Answer
If no edge crossed a nonempty proper subset, there would be no path from that subset to its complement, contradicting connectivity.
Exercise 3.7.11
(A graph has tree edges of weights and non-tree edges of weights . Is minimum? Is it unique? Exhibit an alternative if one exists.)
Core
Use the cycle certificate for each non-tree edge.
Solution(3)
- 1
Compare with its tree path
Key step
The tree path from to is , with maximum weight , and . The comparison holds with equality.
Because: A non-tree edge must weigh at least the heaviest edge on its tree path.
- 2
Compare with its tree path
The tree path from to is , with maximum weight , and .
- 3
Read off minimality and uniqueness
Both inequalities hold, so is minimum. The equality at allows replacing by , which gives , another spanning tree of the same weight . So is minimum but not unique.