- Current
- In the tree
- Would close a cycle
Kruskal's algorithm
Kruskal's algorithm builds a minimum spanning tree, the cheapest set of edges that connects every node, in the simplest way imaginable: take the edges from shortest to longest, and keep each one unless it would close a cycle. Step through to see separate pieces grow and merge into one tree, and the edges that are skipped. Press Play to watch the tree grow, or Step and Back to go one step at a time. Drag the step slider to jump anywhere. The number on each edge is its length. Under the graph are the edges still to try, from shortest to longest; an edge whose ends are already connected would close a cycle and is drawn dashed in red. New graph makes another graph; choose how many nodes and edges it has. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.
How it works
- Press Play, or use Step and Back to move one step at a time.
- Drag the step slider to jump anywhere. The edges still to try are listed under the graph, shortest first.
- Watch for the edges drawn dashed in red: they would close a cycle. New graph makes another graph to try.
How Kruskal's algorithm works
Sort all edges from shortest to longest. Start with every node as a piece of its own. Try the edges in order: if an edge joins two different pieces, it goes in the tree and the two pieces become one; if its two ends are already in the same piece, it would close a cycle, so skip it. Stop when everything is one piece, which happens after one edge fewer than there are nodes, often long before the last edge is tried.
Union-find
For every edge, Kruskal's algorithm has to ask whether its two ends are already connected. A union-find structure answers that quickly: every piece has one representative node, find follows the links to it, and union links one representative to the other. With two simple tricks, path compression and union by size, each question takes almost constant time, so sorting the edges is the slowest part, with work that grows with E log E.
Frequently asked questions
What is Kruskal's algorithm?
A greedy algorithm that builds a minimum spanning tree by sorting all edges from shortest to longest and adding each edge that does not close a cycle with the edges already chosen.
How does Kruskal's algorithm detect a cycle?
An edge closes a cycle exactly when its two ends are already connected by chosen edges. A union-find structure keeps track of which nodes are connected and answers that question almost instantly.
Why does Kruskal's algorithm work?
Because of the cycle property: the longest edge on any cycle is never needed for a minimum spanning tree. Every edge Kruskal skips is the longest on the cycle it would close, since all edges before it were shorter or equal.
When should I use Kruskal instead of Prim?
Kruskal's algorithm is simple and fast on sparse graphs, and works directly on a plain list of edges. Prim's algorithm suits dense graphs and graphs stored as adjacency lists. Both find a tree of the same total length.
Is my graph sent anywhere?
No. The graph is made and the tree is built in your browser, and your last settings stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor