Skip to content
Lizely

Minimum Spanning Tree Solver

Find an exact minimum-weight tree connecting every named node with deterministic Kruskal selection and explicit disconnected-graph errors.

Privacy: your files never leave your device. All processing happens locally in your browser.

How to use

  1. 1.List 2–50 unique node names separated by commas.
  2. 2.Add each undirected edge as from, to, weight using declared node names.
  3. 3.Build the MST, confirm connectivity and modeling assumptions, then copy the selected V−1 edges.

About Minimum Spanning Tree Solver

Minimum Spanning Tree Solver finds a lowest-total-weight set of undirected edges that connects every named node without cycles. Enter comma-separated node names and edge rows as from, to, weight. The result lists the selected edges and total weight. All processing stays in the browser, and the tree can be copied as plain text.

A spanning tree of a connected undirected graph reaches every vertex, contains no cycle, and has exactly V−1 edges. A minimum spanning tree, or MST, has the smallest possible sum of edge weights among all spanning trees. It minimizes the entered abstract edge total; it does not claim that each individual route is shortest. Princeton Algorithms documents these definitions and the Kruskal procedure used here.

Kruskal sorts edges from lightest to heaviest. It adds an edge when its endpoints currently belong to different connected components and skips it when adding it would form a cycle. A disjoint-set union structure tracks components efficiently. Once V−1 edges have been accepted, the selected set is a minimum spanning tree. Equal weights retain input order, making one valid optimum deterministic when several MSTs exist.

Node names are case-insensitively unique. Every edge endpoint must match a declared node. The graph is undirected, so A,B and B,A are duplicate pairs and are rejected rather than silently competing. Self-loops cannot help a spanning tree and are rejected. Weights may be positive, zero, or negative because Kruskal remains valid for finite real edge weights.

The graph must be connected. If separate components cannot be joined with the entered edges, no spanning tree exists and the page displays an explicit error instead of returning a misleading forest. The browser limits input to 50 nodes and 500 edges for responsive interaction. Labels cannot contain commas because commas delimit fields.

An MST is not a route that starts somewhere and visits every node, and it is not a shortest path between a chosen pair. It also ignores direction. Use a traveling-salesperson model for a closed visit order, Dijkstra-style shortest paths for point-to-point distances with suitable weights, or directed-arborescence methods when edge direction matters.

Eight hand-audited goldens cover two-node boundaries, triangles, tied weights, zero and negative weights, a five-node cycle, and connected components joined by one costly bridge. Tests assert V−1 selected edges and exact totals. A disconnected graph is required to fail. These checks catch implementations that simply choose the cheapest edges without preventing cycles.

Use this tool for algorithm study, small network-design drafts, cable-layout examples, or verifying a manual Kruskal trace. Real infrastructure planning needs geography, redundancy, capacity, reliability, regulations, existing assets, and construction constraints. A minimum scalar-weight tree has no redundancy and can be operationally fragile, so validate the model before acting.

Parallel edges are outside this simplified input contract. If alternatives connect the same endpoints, preselect an effective weight or model them with additional nodes, and record that decision so a discarded option is not mistaken for an algorithm choice.

Methodology & sources

Normalize unique node names, validate up to 500 unique undirected finite-weight edges, stably sort by weight and input order, then use disjoint-set union to accept only component-joining edges. Require exactly V−1 selected edges or report a disconnected graph.

Frequently asked questions

Is the result always minimum?
Yes for the entered connected undirected graph and finite edge weights; tied graphs may have several equally minimum trees.
Can weights be negative?
Yes. Kruskal remains valid, and useful negative edges are selected without creating cycles.
Why does a disconnected graph fail?
No spanning tree can reach every node unless the graph is connected.
Is this a shortest route through all nodes?
No. An MST is a branching connection structure, not a visit order or pairwise shortest path.

Related tools

Calculators guides

View all