- Current
- In the tree
- Next to the tree
- Best edge so far
- Would close a cycle
Minimum spanning tree
You want to connect every town with cable, every house with water pipes, or every computer in a network, using as little material as possible. The answer is a minimum spanning tree: the set of edges that connects every node at the lowest total length. Pick Kruskal's or Prim's algorithm and step through to see the tree grow, one shortest allowed edge at a time. 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. Pick the algorithm: Kruskal tries the edges from shortest to longest, Prim grows one tree from the start; click a node to make it Prim's start. The number on each edge is its length. Under the graph is the list of edges still to try, or the nodes waiting to join with the length of their best edge to the tree. 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
- Pick Kruskal's or Prim's algorithm. For Prim, click a node to make it the start.
- Press Play, or use Step and Back to move one step at a time. Drag the step slider to jump anywhere.
- Watch the edges join the tree and the total length grow. New graph makes another graph to try.
Kruskal's algorithm
Sort all edges from shortest to longest and try them in that order. If an edge joins two pieces that are not connected yet, it goes in the tree. If its two ends are already connected through the tree, it would close a cycle, so it is skipped. Stop when the tree has one edge fewer than there are nodes. To tell quickly whether two nodes are already connected, Kruskal's algorithm keeps the pieces in a union-find structure.
Prim's algorithm
Start with a tree of one node. Every node outside the tree remembers its shortest edge to the tree. Repeatedly add the node whose edge is the shortest, together with that edge, and check its edges: one may give a neighbour a shorter way into the tree. Prim's algorithm looks like Dijkstra's algorithm, but it compares single edges, not whole distances from the start. Both algorithms always end with the same total length.
Frequently asked questions
What is a minimum spanning tree?
For a connected graph whose edges have lengths, a spanning tree is a set of edges that connects all the nodes without any cycle; with n nodes it always has n − 1 edges. A minimum spanning tree is a spanning tree whose total length is as small as possible.
What is the difference between Kruskal's and Prim's algorithm?
Kruskal's algorithm looks at the edges of the whole graph from shortest to longest and joins separate pieces into one tree. Prim's algorithm grows a single tree from a start, always adding the shortest edge that leaves it. Both are greedy and find a tree of the same total length; Kruskal suits sparse graphs, Prim dense ones.
Is the minimum spanning tree unique?
When all edge lengths are different, yes. When some lengths are equal, there can be several trees with the same smallest total, and the algorithms may pick different ones depending on how they break ties.
Is a minimum spanning tree the same as shortest paths?
No. The minimum spanning tree keeps the total length of all edges small, but the path between two nodes in the tree can be much longer than their shortest path. For shortest paths, use Dijkstra's algorithm.
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