What is the difference between Kruskal's and Prim's algorithms?

Kruskal's algorithm sorts all edges and adds them in increasing weight order, skipping any that would form a cycle, using union-find to detect cycles. Prim's algorithm grows a single connected tree from a start vertex, repeatedly adding the cheapest edge leaving the current tree, using a priority queue. Both produce a minimum spanning tree.

Is the minimum spanning tree unique?

If all edge weights are distinct, the minimum spanning tree is unique. When some weights are equal, there can be several different minimum spanning trees, all with the same minimum total weight.

Minimum Spanning Trees

A minimum spanning tree connects all vertices of a weighted, connected graph with the smallest possible total edge weight; greedy algorithms such as Kruskal's and Prim's compute one efficiently.

Troba un tema amb PaperMindAviatFind papers & topics

Tools & resources

Baixa les diapositives

Learn & explore

VídeoAviat

Definition

A minimum spanning tree of a connected, edge-weighted graph is a subset of edges that connects all vertices, contains no cycle, and has minimum total weight among all such spanning trees.

Scope

This topic covers the minimum-spanning-tree problem and its classic greedy solutions — Kruskal's algorithm, which adds edges in increasing weight order using a disjoint-set structure, and Prim's algorithm, which grows a single tree using a priority queue — together with the cut and cycle properties that prove these algorithms correct. It also touches on the supporting disjoint-set (union-find) data structure.

Core questions

What is a spanning tree, and what makes one of minimum weight?
Why do greedy edge additions yield a globally minimum spanning tree?
How do the cut property and cycle property justify MST algorithms?
How do Kruskal's and Prim's algorithms differ in strategy and data structures?
How does the disjoint-set (union-find) structure make Kruskal's algorithm efficient?

Key concepts

spanning tree
cut property
cycle property
Kruskal's algorithm
Prim's algorithm
disjoint-set (union-find)
greedy safe edge
edge weights

Key theories

Cut property: For any partition of the vertices into two sets, the minimum-weight edge crossing the partition belongs to some minimum spanning tree; this safe-edge guarantee is the correctness basis for both Kruskal's and Prim's greedy algorithms.
Disjoint-set union-find support: Kruskal's algorithm uses a union-find structure with union by rank and path compression to test, in nearly constant amortized time, whether adding an edge would create a cycle.

Clinical relevance

Minimum spanning trees model least-cost network design: laying out communication, electrical, or transportation networks that connect all sites cheaply. They also serve as building blocks in clustering, image segmentation, approximation algorithms for the traveling salesman problem, and the analysis of point sets.

History

The minimum-spanning-tree problem was first solved by Otakar Borůvka in 1926 for electrical-network design. Vojtěch Jarník (1930) and later Prim (1957) and Dijkstra developed the tree-growing approach, while Kruskal (1956) gave the edge-sorting greedy method, making this one of the earliest well-understood combinatorial optimization problems.

Key figures

Joseph Kruskal
Robert Prim
Otakar Borůvka
Vojtěch Jarník

Seminal works

kruskal1956
cormen2009

Frequently asked questions

What is the difference between Kruskal's and Prim's algorithms?: Kruskal's algorithm sorts all edges and adds them in increasing weight order, skipping any that would form a cycle, using union-find to detect cycles. Prim's algorithm grows a single connected tree from a start vertex, repeatedly adding the cheapest edge leaving the current tree, using a priority queue. Both produce a minimum spanning tree.
Is the minimum spanning tree unique?: If all edge weights are distinct, the minimum spanning tree is unique. When some weights are equal, there can be several different minimum spanning trees, all with the same minimum total weight.