What is a minimum spanning tree?

A spanning tree connects every node of a graph without forming a cycle, using exactly N-1 edges for N nodes. The minimum spanning tree is the spanning tree whose total edge weight is as small as possible.

How do Kruskal's and Prim's algorithms differ here?

Kruskal sorts all edges by weight and greedily adds the cheapest edge that does not create a cycle, using a Union-Find structure to detect cycles. Prim grows a single tree from node 0, always adding the cheapest edge that reaches a node outside the current tree.

Minimum Spanning Tree — Kruskal & Prim (2D)

Algorithm

Graph

Nodes 22

Playback

Speed (steps/s) 7

Live readout

Total edges

–

MST edges

Step

MST weight

–

Status

Press Play or Step to start.

How it works

Both algorithms are unmodified textbook greedy strategies for finding the minimum spanning tree of a weighted graph:

Kruskal — sorts every edge by weight, then greedily accepts the next cheapest edge unless it would connect two nodes already joined (a cycle). Cycle detection uses a real Union-Find (disjoint-set) structure with path compression and union-by-rank, so each test runs in near-constant time.
Prim — grows a single tree from node 0, at each step scanning every edge leaving the current tree and adding the cheapest one that reaches a node not yet in the tree.

Both always finish with exactly N−1 edges and identical total weight — a consequence of the cut property of spanning trees — even though they explore the graph in completely different orders.

Unprocessed Candidate In MST Rejected