Minimum Spanning Tree Finder
Find a minimum spanning tree of an edge-weighted graph using Kruskal's algorithm; disconnected graphs get a minimum spanning forest.
Description
Build a minimum spanning tree—or a minimum spanning forest for disconnected data—from weighted undirected edges.
A minimum spanning tree connects every vertex of a connected weighted graph while minimizing total edge weight and avoiding cycles. Typical applications include approximate network layout, cable planning, cluster structure, and selecting a low-cost backbone.
When to use Minimum Spanning Tree Finder
- Choose a minimum-cost set of links that connects a network
- Inspect the forest produced by disconnected components
- Compare a spanning backbone with shortest-path routing
How the calculation works
The finder uses Kruskal's algorithm. It sorts finite weighted edges from lightest to heaviest, skips self-loops, and uses union-find to accept an edge only when it joins two previously separate components. Optional declared nodes preserve isolated vertices.
Interpreting the result
`treeEdges` identifies the selected endpoint pairs, `totalWeight` sums their weights, and `edgeCount` reports how many links were chosen. A `componentCount` of one means the graph was connected; a larger value means the result is a minimum spanning forest.
Important limitations
- Edges are treated as undirected even though each pair is entered in an order.
- When several trees have the same minimum weight, deterministic name ordering selects one valid answer.
- A spanning tree minimizes the combined backbone weight, not the route length between every pair of nodes.