A spanning tree of a connected graph is a set of edges that links every node together without forming any cycle. When the edges carry weights, the minimum spanning tree is the spanning tree whose total edge weight is as small as possible. Joseph Kruskal opened his 1956 paper on the subject by considering “a connected graph G with N nodes” and lengths assigned to its edges, asking for the shortest spanning subtree.
Kruskal’s 1956 paper, “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem” in the Proceedings of the American Mathematical Society, gives a greedy construction: consider the edges in order of increasing length and add each one to the growing forest unless it would create a cycle, until all nodes are joined. The result is a minimum spanning tree, and Kruskal noted that when all edge lengths are distinct the shortest spanning tree is unique.
The following year, Robert Prim published “Shortest Connection Networks and Some Generalizations” in the Bell System Technical Journal (1957). Prim’s method grows a single tree outward from a starting node, at each step adding the cheapest edge that connects a node already in the tree to one still outside it. Both approaches are greedy, repeatedly making a locally cheapest safe choice, and an efficient implementation of Prim’s method relies on a priority queue to find that cheapest connecting edge quickly.
Minimum spanning trees answer a practical question that Prim framed directly: how to interconnect a set of terminals with the least total length of links. They are applied in designing communication, power, and transport networks where wiring or cabling cost matters, and they also serve as a building block in clustering, where cutting the most expensive edges of the tree separates data into natural groups.