This simulation animates two classic greedy algorithms — Kruskal's and Prim's — that compute the minimum spanning tree (MST) of a weighted graph: the subset of edges that connects every node while keeping the total edge weight as low as possible. Nodes are scattered across the canvas and joined to their nearest neighbours, with each edge carrying a numeric cost. Watching the tree grow edge by edge reveals how very different strategies arrive at the same optimal structure, a result guaranteed by the cut property of spanning trees.
A random weighted graph of 8–40 nodes, each linked to roughly its four nearest neighbours, with weights derived from screen distance. Kruskal's algorithm sorts all edges by weight and adds the cheapest one that does not form a cycle, using a Union-Find (disjoint-set) structure to detect cycles. Prim's algorithm instead grows a single tree from node 0, repeatedly adding the cheapest edge that reaches an unvisited node. Both finish with exactly N−1 edges and the same minimum total weight.
Toggle between Kruskal and Prim, then set the node count with the Nodes slider (8–40). Choose Slow, Normal or Fast playback speed. Press Play to animate continuously or Step to advance one decision at a time, watching candidate (yellow), accepted (green) and rejected (red) edges. New Graph regenerates a fresh layout. The side panel tracks node count, total edges, MST edges and running MST weight.
Both algorithms are provably optimal, yet Kruskal's was published in 1956 while Prim's dates to 1957 (and was first described by Jarník in 1930). On a graph with unique edge weights the minimum spanning tree is unique, so Kruskal and Prim always converge on the identical set of edges despite exploring in completely different orders.
A spanning tree is a set of edges that connects every node of a graph without forming any cycle, which for N nodes always uses exactly N−1 edges. The minimum spanning tree is the spanning tree whose edge weights sum to the smallest possible total. It is widely used to design low-cost networks such as cabling, pipelines and road links.
Kruskal's algorithm is edge-centric: it sorts every edge by weight and greedily adds the next cheapest edge as long as it does not create a cycle, using a Union-Find structure to test connectivity. Prim's algorithm is node-centric: it starts from one node and always extends the existing tree with the cheapest edge to an unvisited node. They explore in different orders but produce the same optimal weight.
Each edge is labelled with its integer weight, computed from the distance between its two nodes. Faint edges are unprocessed, yellow edges are current candidates, green edges have been accepted into the tree and red edges were rejected for creating a cycle. In Prim mode, filled green nodes are those already part of the growing tree.
Kruskal considers edges from cheapest to most expensive, but adding an edge between two nodes that are already connected would create a cycle rather than extend the tree. The Union-Find structure detects this in near-constant time, so such an edge is marked rejected (red) and skipped, ensuring the result stays a valid tree.
Both always produce a minimum spanning tree, so the total weight is identical. When all edge weights are distinct the MST itself is unique, meaning Kruskal and Prim select exactly the same edges. If some weights are tied, the chosen edges may differ slightly, but the overall minimum weight is still the same.