Minimum Spanning Tree Generator

What this generator does

Builds a connected weighted graph, runs Kruskal's algorithm, and shows every edge with the accept-or-reject decision that produced the tree. Where the edge count allows it also enumerates all spanning trees and confirms the weight is genuinely the minimum.

How to use this tool

1. Choose how many nodes and how dense the extra edges should be.
2. Work through the edges in weight order, skipping any that would close a cycle.
3. Compare your tree against the one shown, edge by edge.
4. Seed the graph to set the same problem twice.

Understanding the controls

How many nodes

Between 4 and 12. The exhaustive confirmation runs while the graph has at most twenty edges, which covers the smaller sizes.

Extra edge density (%)

How many edges beyond the ones needed to connect everything. More edges means more rejected candidates and a more interesting run.

Seed

Any word reproduces the same graph and the same weights, so a problem can be set and marked later.

Common use cases

• Worked examples for teaching Kruskal or Prim with a known answer
• Showing that a greedy rule can be exactly right, which is rare
• Test instances for a spanning-tree implementation
• Network-cost questions where the cheapest connection matters
• Setting the same graph for two people from a seed

How this generator works

The graph is built as a random spanning tree plus extra edges, which guarantees connectivity without retrying. Kruskal then sorts every edge by weight and uses union-find to reject the ones whose ends are already joined. The check confirms the result has exactly one fewer edge than nodes, contains no cycle, spans everything, and — where affordable — matches an exhaustive search.

Randomness and fairness

The graph and its weights are random; the minimum spanning tree is computed and, at small sizes, proved. Seeded graphs reproduce exactly and are therefore explicitly not cryptographically secure. Without a seed the browser's cryptographically secure generator is used.

For how randomness is produced across the whole site, see how Generate Random works.

Limitations and good to know

• Edge weights are small whole numbers, which keeps the arithmetic checkable rather than realistic.
• The exhaustive confirmation stops above twenty edges, where two-to-the-edges subsets become too many.
• Only undirected graphs — directed minimum spanning trees are a different and harder problem.
• Ties between equal weights are broken by edge order, so a different but equally cheap tree may exist.
• A generated graph is gone on reload; the seed is what redraws it.

Privacy and your data

The graph and the tree are computed entirely in your browser. Nothing about the problem or your seed is transmitted or kept.