Prim and Kruskal: Two Greedy Roads to the Minimum Spanning Tree

The minimum spanning tree asks for connectivity without unnecessary total cost

Given a connected weighted undirected graph, a spanning tree connects every vertex while containing no cycle. The minimum spanning tree, or MST, is the spanning tree whose edge weights sum to the least possible total. The problem models situations such as choosing links for a communications network when every location must be connected but duplicate routes are not required. What made MST historically important was not just the application. It became a canonical demonstration that a greedy algorithm—making locally attractive choices without backtracking—can nevertheless be globally optimal under the right structural property.

The absence of cycles makes every selected edge consequential

A spanning tree on V vertices contains exactly V-1 edges. Adding one edge creates a cycle; removing one disconnects the tree. The algorithm therefore has little room for arbitrary choices.

Kruskal’s 1956 algorithm grows a forest by accepting the cheapest safe edge

Joseph B. Kruskal published “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem” in 1956.^[1] The method considers edges in increasing weight order and accepts an edge when it connects two previously separate components. NIST summarizes the algorithm as maintaining a set of partial minimum spanning trees and repeatedly adding the shortest edge whose endpoints lie in different trees.^[2] The result starts as isolated vertices, becomes a forest and ends as one spanning tree.

Prim’s 1957 algorithm grows one connected tree outward

Robert C. Prim’s 1957 Bell System Technical Journal paper studied the problem of interconnecting terminals by a shortest network and gave practical procedures for solving it.^[3] The same algorithmic idea had been published earlier by Vojtěch Jarník in 1930, which is why NIST names the method the Prim-Jarník algorithm.^[5] Prim’s familiar formulation starts from one vertex and repeatedly chooses the cheapest edge crossing from the growing tree to a vertex outside it. Unlike Kruskal’s scattered forest, it maintains one connected component throughout. The final object can be the same even though the intermediate states look completely different.

The two algorithms disagree about what must remain connected during construction

Prim keeps chosen edges connected from the beginning. Kruskal permits many disconnected partial trees and merges them only when a cheap edge links two components.

The cut property explains why both greedy strategies are safe

MIT’s treatment of minimum spanning trees develops the cut property behind these algorithms.^[4] Consider any partition of the vertices into two groups. A lightest edge crossing that cut is safe for some MST under the standard conditions. Prim repeatedly uses a cut separating the current tree from the remaining vertices. Kruskal uses cuts induced by the components of its forest. The algorithms therefore look different operationally but rely on the same structural fact: a locally light crossing edge can be chosen without sacrificing global optimality.

Kruskal turns cycle detection into the central implementation problem

Because Kruskal processes edges globally by weight, it needs an efficient way to decide whether adding an edge would join two different components or create a cycle inside one component. The disjoint-set union data structure became the natural companion: find operations identify component representatives, and union merges components after an accepted edge. NIST’s definition captures the conceptual rule even when it leaves implementation details open.^[2] This pairing is an important historical pattern—an algorithm’s asymptotic performance can depend on a separate data structure designed specifically to support its repeated test.

Sorting edges front-loads Kruskal’s main cost

Once edges are in nondecreasing order, component maintenance determines whether each candidate is safe. This makes Kruskal particularly natural for sparse graphs represented as edge lists.

Prim turns frontier selection into the central implementation problem

Prim repeatedly needs the cheapest edge that reaches a vertex outside the current tree. With adjacency lists, a priority queue can track the cheapest known attachment for each unchosen vertex. MIT’s MST lecture compares how different priority-queue choices affect running time and emphasizes that the abstract greedy rule is distinct from the data structure used to realize it.^[4] Prim is therefore a good example of algorithm engineering: the correctness proof follows the cut property, while performance depends on how efficiently the frontier is maintained.

The algorithms became a standard proof that greedy does not mean heuristic

MIT’s MST treatment presents Prim and Kruskal as canonical greedy algorithms whose local edge choices can be proved safe through cut-based reasoning.^[4] This distinction matters. In many optimization problems, greedy choices are only heuristics and can miss the best solution. MST has special exchange and cut properties that justify the strategy rigorously. The algorithms became foundational classroom examples because their proofs make the difference between “seems reasonable” and “provably safe” unusually visible.

Greedy correctness comes from structure, not optimism

The algorithm is trustworthy only because a mathematical property shows how a local edge can be exchanged into an optimal solution without increasing total cost.

Why Prim and Kruskal belong together in algorithmic history

Prim and Kruskal belong together because they show two different operational interpretations of the same optimization structure. Kruskal sorts the entire edge set and merges components; Prim commits to one component and expands its boundary.^[1][3] Both exploit safe edges crossing cuts, and both produce a minimum spanning tree without exploring the exponential number of possible spanning trees.

Their coexistence is also a lesson in engineering choice. Graph density, representation and available data structures can make one implementation more attractive than the other even though both solve the same abstract problem. Algorithm selection therefore includes understanding not only complexity classes but the shape of the input and the cost of supporting operations.

Most importantly, the two algorithms helped establish greedy design as a rigorous paradigm. They demonstrate that local choice can be globally correct when the problem supplies the right exchange property. That insight reaches far beyond spanning trees and remains one of the central patterns in algorithm design.

RESEARCH / PROVENANCE

Works Cited

5 SOURCES

1. 01
   Kruskal — On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem ↗doi.org
2. 02
   NIST DADS — Kruskal's Algorithm ↗nist.gov
3. 03
   Prim — Shortest Connection Networks and Some Generalizations ↗doi.org
4. 04
   MIT OpenCourseWare — Greedy Algorithms: Minimum Spanning Tree ↗ocw.mit.edu
5. 05
   NIST DADS — Prim-Jarnik Algorithm ↗nist.gov

CodeHistory is a living archive. Citations document the evidence used for this edition; later evidence may refine the account.