Minimum spanning tree
Find low-cost connections with Kruskal and inspect its union–find decisions.
About this tool
Connect nodes at minimum total weight, without cycles. Enter one undirected edge per line: A B 4. A alone adds an isolated node. Blank lines and lines starting with # are ignored. IDs use 1–24 ASCII letters, digits, underscores, periods or hyphens. Weights use a decimal point and optional exponent; negative and zero weights are valid. Limits: 24 nodes, 80 different edges, 12,000 characters, weights from −1e9 to 1e9. A B 4 and B A 4 are one edge; different weights between the same nodes remain parallel edges.
Calculate produces the result immediately; Step examines one edge. Optional animation uses 0–2000 ms, initially 350. Pause/Resume keeps the current run. Calculate can finish a paused run. Reset or edited inputs discard the run; raw graph and delay drafts are saved locally, including unfinished or invalid inputs. Reload restores inputs without calculating; progress is not saved.
Kruskal considers edges by increasing weight. Union–find accepts an edge only when its endpoints are in different components; otherwise it would create a cycle. Rank-based union and path halving implement the component lookup. Equal weights are ordered by the sorted, case-sensitive node IDs. Other minimum trees may be equally valid. Sorting costs O(E log E), with near-constant amortized union–find operations. All edges are examined to show rejected cycles, even after the tree has formed.
The original network has total weight 13: B–C 1, B–D 2, E–F 2, A–C 3, C–E 5. Disconnected inputs produce one minimum tree per component, including isolated nodes: a minimum spanning forest. This is not a shortest-path or travel-route solver. Self-loops are always rejected. Geometric edge length has no relation to its weight.
Six node colors help identify components and repeat for larger sets; exact membership is in the table. Selected edges are green, rejected edges dashed red; the current edge is thicker. Selected edges, exact component membership and examined decisions are available as tables. Long IDs use table numbers in the graph; over 16 nodes the graph scrolls locally. Dense edges can overlap. Floating-point arithmetic is used; displayed weights have up to 12 significant digits.