Minimum Spanning Tree Calculator screenshot

Minimum Spanning Tree Calculator

Build a minimum spanning tree from a weighted edge list with Kruskal's algorithm, and print the accepted edges, the total weight and the component count.

Privacy First
0 Runs
Updated 2026-11-22
Runs in your browser
No sign-up, no upload
Provably minimal

Minimum Spanning Tree Calculator

Build a minimum spanning tree from a weighted edge list with Kruskal's algorithm, and print the accepted edges, the total weight and the component count.

How this page computes

The list is reduced to one entry per undirected pair at its lightest weight, then sorted by weight and node name. A union-find structure over the node names decides whether an edge joins two components.

Accepted edges are collected with their weights, and the roots left at the end give the component count. The total is the sum of the accepted weights, printed with the same precision as the input.

The calculation runs entirely in this browser tab; nothing is uploaded.

The page connects every node of an undirected graph as cheaply as possible. On A-B 4, B-C 2, A-C 5 it keeps B-C at 2 and A-B at 4 for a total of 6, and drops A-C at 5 because those three nodes are already connected.

Kruskal's rule is what makes the answer provably minimal: take the lightest edge that joins two different components, and skip any edge whose endpoints are already joined. A disconnected graph yields a minimum spanning forest, one tree per component, and the page says so.

How to use Minimum Spanning Tree Calculator

Type one edge per line and press Run. The output lists the chosen edges in the order they were accepted, with each weight, so the greedy steps can be followed.

The component count tells you whether the tree spans everything. A count above 1 means the graph is disconnected and the printed edges form a forest rather than one tree.

Why the lightest joining edge is always safe

Sort the distinct pairs by weight, lightest first. Walk the sorted list and accept an edge only when its two endpoints belong to different components; joining them merges the components. After n − 1 acceptances one tree spans n nodes, or the list runs out and the graph is disconnected.

The exchange argument is the reason this is optimal: any spanning tree that omits the lightest joining edge can swap a heavier edge for it without disconnecting, so no cheaper tree exists. The page prints the total so the claim can be checked against a hand-built tree.

What to Expect

Best for

  • Cheapest set of connections that keeps a network in one piece
  • Checking a Kruskal or Prim exercise
  • Seeing which edges a greedy walk rejects and why

Not ideal for

  • Directed graphs, where the right structure is an arborescence
  • Finding a path between two specific nodes
  • Graphs whose weights are negative costs of a different kind

What this tool keeps

  • Every weight, and the lighter of any duplicated pair

What may need cleanup

  • Nothing: the edge set and the total are final

Common errors

  • A negative weight is refused with its line number
  • A duplicated pair keeps the lighter weight, invisible in the total but visible in the count

Example use cases

  • Connect four offices at the lowest cabling cost
  • Check that a three-node triangle uses its two lightest edges
  • See a disconnected graph reported as a forest

Sample input

edges A-B 4, B-C 2, A-C 5

Sample output

B-C (2) and A-B (4), total weight 6, one component

Who this is for

  • Students learning greedy algorithms
  • Network planners comparing layouts

Frequently asked questions

Why is A-C not in the tree?

Because A and C are already connected through B by the time A-C is considered. Adding it would close a cycle, and a spanning tree has no cycles, so Kruskal skips it even though it is a real edge of the graph.

What if the graph is disconnected?

The page prints a minimum spanning forest: the cheapest tree for each component, and the component count in the output. It does not invent an edge to join the pieces.

Is the tree unique?

Only when the weights are distinct. Equal weights can give several trees of the same total, and the page prints the one Kruskal finds with ties broken by node name, so the output is reproducible.

Developer program

Build custom tools for your store

Join the SDK program to create useful ecommerce utilities for your store.