Kruskal
Kruskal sorts the edges cheapest first and then considers each in turn. An edge whose two ends are already in the same group would close a cycle, so it is rejected; an edge joining two different groups is taken, and the two groups merge. When one group is left, its edges are a minimum spanning tree. The groups are kept in a union-find, which answers "are these two in the same group?" in almost constant time.
Its frontier
A sorted edge list, and the disjoint sets themselves.
When it is the right choice
Whenever the cheapest set of links that connects everything is what is wanted: laying cable, clustering by nearest neighbour, building a maze. It is the natural choice when the edges are already sorted or easy to sort, and when the graph is sparse. On a disconnected graph it produces a spanning forest rather than failing, which is usually the right behaviour.
How it works
- Start with every node in a group of its own.
- Sort the edges by weight, cheapest first.
- Take the next edge and ask whether its two ends are in the same group.
- If they are, it would close a cycle: reject it.
- If they are not, take it into the tree and merge the two groups.
- Stop when one group is left, or when the edges run out.
Worth noticing
- The disjoint sets are the second track, and they are the point. Colouring only the chosen edges would show the result and hide the reason — every rejection on this page is a rejection because two node names already sit in one set.
- The rejected counter is not waste. An edge rejected for closing a cycle is information: it says the two ends are already connected more cheaply.
- Kruskal takes edges from anywhere in the graph, so for most of the run the tree is several disconnected pieces. Prim, on the same graph, keeps one connected piece throughout. The final weight is the same.
Cost
- Best
- O(E log E)
- Average
- O(E log E)
- Worst
- O(E log E)
- Extra space
- O(V)
- Runs on
- a weighted undirected graph
- Largest grid
- 11 by 7 cells
- Largest graph
- 14 nodes, 28 edges
The limits are pedagogical rather than technical: this tool keeps a cost and a predecessor for every node in every recorded step, so the size of the graph sets the size of the trace directly, and a run has to stay short enough to sit and watch. A graph that would take more than three thousand steps on this algorithm is refused before a single step is generated, from a formula in the number of nodes and edges rather than by running it and finding out.
Graphs are generated from a seed, so the link in your address bar draws exactly the graph on your screen — no part of it is random in a way a reload could change.