A minimum spanning tree (MST) of a connected, undirected, weighted graph is a set of V−1 edges — where V is the number of nodes — that connects every node without forming any cycle and that has the smallest possible sum of edge weights. Solving a minimum spanning tree problem means finding that optimal edge set. The classic, deterministic way to do it is Kruskal's algorithm, which sorts every edge by weight from lightest to heaviest, then walks through the list adding each edge only when its two endpoints currently belong to different components and skipping it when they already do, because adding it would close a cycle. A disjoint-set union structure tracks components efficiently. Once exactly V−1 edges have been accepted, you have a minimum spanning tree. When several equally minimum trees exist, deterministic tie-breaking by input order picks a single valid answer. The Minimum Spanning Tree Solver runs this procedure in the browser, validates every input rule, and returns a copyable edge list with the total weight.
What a Minimum Spanning Tree Problem Actually Is
The minimum spanning tree problem is a combinatorial optimization problem on a graph. A graph is a set of nodes, also called vertices, joined by edges. In a weighted graph, each edge carries a number — a cost, a length, a capacity, or any scalar label that the modeler wants to minimize. The graph must be connected, meaning there is at least one path between any two nodes, and the edges are undirected, meaning they work the same way in both directions.
A spanning tree of such a graph is a subset of edges that reaches every node (spans), contains no cycle (is a tree), and has exactly V−1 edges, where V is the node count. The minimum spanning tree is the spanning tree whose summed edge weight is as small as possible. The MST only minimizes the entered total weight; it does not say any individual edge is the shortest route between its endpoints, and it does not describe a visit order. Princeton's Algorithms course on minimum spanning trees documents both the definition and the Kruskal procedure, and the solver in this article follows that contract.
How Kruskal's Algorithm Builds the Tree
Kruskal's algorithm is the standard greedy approach, and it is the one this tool implements. The procedure is straightforward enough to verify by hand on small cases:
- Normalize every node name so casing differences (A versus a) are not treated as different nodes.
- Validate edges: reject self-loops, reject duplicate undirected pairs (A,B and B,A are the same edge), and require every endpoint to be a declared node.
- Sort the surviving edges stably by weight, with original input order as the tie-breaker. This deterministic step is what makes one valid optimum reproducible when several MSTs exist.
- Initialize a disjoint-set union (union-find) structure so each node starts alone in its own component.
- Walk the sorted list. For each edge, check whether its two endpoints are in different components. If yes, add the edge to the tree and union the two components. If no, skip the edge because it would form a cycle.
- Stop when V−1 edges have been accepted. If the list is exhausted before V−1 edges are accepted, the graph is disconnected and no spanning tree exists.
Princeton's reference implementation of KruskalMST follows exactly this sequence, and the tool's behavior matches the published source.
Solve a Minimum Spanning Tree Problem With This Tool
The Minimum Spanning Tree Solver runs the steps above in the browser, so no data leaves the page. To use it:
- Open the Minimum Spanning Tree Solver and list 2 to 50 unique node names in the nodes field, separated by commas. Node names are case-insensitively unique, so Hub, hub counts as one node and triggers a validation error.
- Add each undirected edge on its own row as from, to, weight. Both endpoints must exactly match a declared node, and the weight is a finite real number that may be positive, zero, or negative.
- Click the build button. The solver normalizes names, rejects self-loops and duplicate A,B / B,A pairs, sorts the surviving edges, and runs the union-find loop.
- Confirm the connectivity check passes. The page shows an explicit "disconnected" error if the edges cannot reach every node, rather than returning a misleading partial forest.
- Copy the V−1 selected edges from the result panel as plain text. Each row shows its endpoints and weight, and the panel also reports the total weight.
Worked Example: A Four-Node Graph
To see the procedure produce a real answer, consider four nodes — A, B, C, D — joined by five weighted edges:
| from | to | weight |
|---|---|---|
| A | B | 1 |
| A | C | 4 |
| B | C | 3 |
| B | D | 2 |
| C | D | 5 |
Sorted by weight (and kept in input order on ties): (A,B,1), (B,D,2), (B,C,3), (A,C,4), (C,D,5).
Walk the list with union-find:
- (A,B,1) — A and B are in different components, accept. Total so far: 1. Components: {A,B}, {C}, {D}.
- (B,D,2) — B and D are in different components, accept. Total so far: 3. Components: {A,B,D}, {C}.
- (B,C,3) — B and C are in different components, accept. Total so far: 6. Components: {A,B,C,D}.
- (A,C,4) — A and C are now in the same component, skip (would form a cycle).
- (C,D,5) — C and D are in the same component, skip.
Three edges accepted — exactly V−1 = 3 for V = 4 — so the result is a minimum spanning tree: {(A,B,1), (B,D,2), (B,C,3)} with total weight 6. Paste those rows into the solver to confirm.
When the MST Solver Is the Wrong Tool
An MST is not a route and it is not a shortest path. Three adjacent problems are easy to confuse with it, and the solver is deliberately not designed to handle them:
| Problem | What it answers | Right tool |
|---|---|---|
| Minimum spanning tree | Acyclic, minimum-total-weight connection of all nodes | This solver |
| Shortest path between two nodes | Minimum-weight walk from one node to another | Dijkstra-style solvers with directed or undirected edges |
| Closed visit order through every node | Route that starts at one node, visits each other node once, and returns | A traveling-salesperson model |
| Minimum-cost one-to-one assignment | Pairing workers to tasks so every worker gets one task at minimum total cost | Hungarian-algorithm solvers such as the assignment-problem walkthrough |
These share the same disciplined input, validation, and result pattern, but they optimize different objectives, so each needs its own model.
Input Rules and Limits to Respect
The solver's input contract is strict on purpose, so model errors become clear messages instead of silently wrong trees:
- 2 to 50 unique node names. Labels cannot contain commas because commas already delimit fields.
- Up to 500 unique undirected edges with finite real weights. Weights can be positive, zero, or negative; Kruskal's algorithm remains valid for all three.
- Self-loops are rejected — they cannot help a spanning tree.
- A,B and B,A are duplicate pairs and are rejected, so the tool does not have to break ties between two definitions of the same edge.
- Parallel edges (two distinct edges between the same endpoints) are outside the simplified input contract. If your model has them, pre-select an effective weight on the source data or model the alternatives with extra nodes, and record that decision so a discarded option is not mistaken for an algorithm choice.
- The graph must be connected. If separate components cannot be joined with the entered edges, the page reports the error and does not return a misleading forest.
- Equal weights retain input order, which keeps the result deterministic when multiple MSTs exist.
These rules catch implementations that simply choose the cheapest edges without preventing cycles, a known footgun in naive MST code.
Using the Result in Practice
For algorithm study and small network-design drafts, the solver is a quick way to check a manual Kruskal trace or to produce a clean example set. Eight hand-audited test cases cover the boundaries that usually break small implementations: two-node graphs, triangles, tied weights, zero and negative weights, a five-node cycle, and connected components joined by one costly bridge. They each assert that exactly V−1 edges are selected and that the total matches a known value, and a disconnected graph is required to fail.
For real infrastructure planning — cable layout, pipelines, road design — the same minimum scalar-weight logic does not cover geography, redundancy, capacity, reliability, regulations, existing assets, or construction constraints. A pure MST is also a single tree with no redundancy, so it can be operationally fragile. The solver is a sound model for the abstract edge-weight question and a useful checkpoint against a hand trace; it is not a substitute for validating the model with the real data it is meant to represent.