How to use the minimum spanning tree calculator
- List the connections, one per line: two place names without spaces, then the cost, distance or weight of linking them, for example A B 4.
- Read the headline for the total cost of the cheapest network that joins every place.
- The first table lists the links to build, in the order they are chosen, with a running total. The second lists links left out because they would close a loop.
- If the places fall into separate groups, the result is a cheapest forest: one tree for each group.
Formula
Kruskal: sort all links by cost, add each link unless its ends are already joined
Prim: grow from one place, always adding the cheapest link to a new place
a spanning tree of n places uses exactly n - 1 links
Both methods give a tree of the same total cost, so the page runs both and shows the second total as a check. When several links cost the same, more than one cheapest tree can exist; the total stays the same.
Five places and seven possible links
The default links are A-B 4, A-C 3, B-C 1, B-D 2, C-D 4, C-E 6 and D-E 5. Kruskal adds B-C (1), B-D (2), A-C (3) and D-E (5), skipping C-D (4) and A-B (4) because they would close loops and C-E (6) because E is already joined.
The total is 1 + 2 + 3 + 5 = 11 with 4 links for 5 places. Prim's method from A reaches the same total of 11. A search over every set of 4 links finds no cheaper tree, so 11 is the minimum.
What a spanning tree is
A spanning tree connects every place without any loops. A minimum spanning tree is the one whose links cost least in total. It answers questions like how to lay cable, pipe or road between sites at the lowest cost when every site must be reachable, but it does not tell you the shortest route between two particular places.
The costs can be distances, prices or any other weight, and they can be negative. Parallel links between the same two places are allowed; the cheaper one is used. A link from a place to itself is rejected.
Related problems
A minimum spanning tree is different from a tour. To visit every place once and return, use the Shortest Route Calculator. To pair people with jobs at least cost, the Assignment Optimizer solves that problem, and for choosing items under a limit, the Knapsack Optimizer. The Linear Programming Solver handles general resource problems.
More math tools
For other numerical methods, try the Polynomial Root Finder, Root Finder and Numerical Integration Calculator.
Assumptions and limits
- Each connection can be used in both directions at the same cost.
- Place names contain no spaces, and up to 200 places and 2,000 links are supported.
- Costs are plain numbers without units, and may be negative or zero.
- Only the total cost is guaranteed to be minimal; the choice among equal-cost links depends on the order you typed them.
Frequently asked questions
Is the cheapest network always unique?
No. When several links share a cost, different trees can have the same total. The total is always the same, even when the chosen links differ.
What if some places cannot be reached from the others?
The result is a spanning forest with one tree for each group of places that are connected, and the page reports how many groups there are.
Does the tree give the shortest route between two places?
Not necessarily. It minimizes the total cost of the whole network. The path between two places inside the tree can be longer than the best direct route.
Why are some links left out?
A link is skipped when its two places are already connected through links chosen earlier, because adding it would create a loop that no network needs.