Minimum Spanning Tree: Network Design (2D)

Algorithm

Controls

Nodes 18

Build speed 3.0 edges/s

Show all candidate links Off

Live Network Cost

Edges placed

0 / 17

Last edge added

—

Total cable length (MST)

0.00

Length saved vs. full mesh

0.0%

How it works

A minimum spanning tree (MST) is the cheapest set of edges that connects every node in a network with no cycles — exactly what a telecom or power-grid engineer wants when laying cable between N sites at minimum total length. For N nodes, an MST always has exactly N−1 edges.

Prim's algorithm (grows one tree):
  T = {start}
  while T != V:
    pick min-weight edge (u,v) with u in T, v not in T
    add v and (u,v) to T

Kruskal's algorithm (grows a forest):
  sort all edges by weight ascending
  for each edge (u,v) in that order:
    if find(u) != find(v):   // union-find, no cycle
      add (u,v);  union(u,v)

Prim's — always expands the single connected tree by its cheapest outgoing edge (green = in tree, amber pulse = edge just added).
Kruskal's — considers every edge globally from shortest to longest, skipping any that would close a cycle (tracked with union–find).
Both provably produce a tree of the same minimum total weight, though the edges chosen along the way can differ — reflected live in the readouts as you switch algorithms.
Show all candidate links reveals the full complete graph in the left-hand site map so you can see how few of them the MST actually needs.

This 2D edition runs the identical Prim's/Kruskal's automaton as the 3D version — same complete graph, same greedy growth — but sites sit on a jittered 2D grid (a facility-layout arrangement, not a camera view of the 3D point cloud) and are paired with a second, genuinely 2D-native representation with no 3D counterpart: a live distance-matrix heatmap. Cell (i,j) brightness encodes the real Euclidean distance between site i and site j; a green outline marks every pair the tree actually keeps, so you can watch the MST pick out a sparse set of short, bright cells from the dense field of long, dim ones.

Real-world use: fiber/road/power network layout, circuit board wiring, clustering (single-linkage), and approximate solutions to the traveling-salesman problem all build on the MST.

In minimum spanning tree Just-added edge Not yet connected Matrix: bright = short distance