Why is the graph complete—would a sparse graph be more realistic?

A **complete Euclidean** graph is a clean teaching model: every pair of sites could be wired in principle, and the MST picks the **cheapest n−1 links** that keep everything connected. Real networks are often sparse with missing edges; the same algorithms apply, but the dense case makes the **Kruskal** sort and the **Prim** “scan all crossing edges” story very explicit.

Does changing the Prim root change the final MST?

The **set of edges** in an MST is not always unique when weights tie, but every MST has the **same total weight**. Here ties are resolved deterministically, so you may see **different edge sets** for different roots if multiple MSTs exist, while the **readout weights** still match **Kruskal**.

What does the red dashed highlight mean in Kruskal mode?

That edge is the **next candidate** in sorted order, but both endpoints already lie in the **same component**, so adding it would create a **cycle**—Kruskal **skips** it.

Minimum Spanning Tree (Prim & Kruskal)

Random planar points, complete Euclidean-weighted graph: step through Prim from a root or Kruskal with union–find; compare total MST weight.

About this model

Vertices are n pseudo-random planar points (reproducible from a layout seed). The simulator treats the graph as complete with nonnegative edge weights equal to Euclidean distances, so every spanning tree has n−1 edges. Prim starts from a selectable root and repeatedly adds the minimum-weight edge with exactly one endpoint already in the growing tree—this is the standard cut property view. Kruskal sorts all edges by weight (ties broken lexicographically on endpoints for determinism), then scans them while maintaining a disjoint-set (union–find) structure: an edge is accepted if it joins two different components and rejected (shown dashed red) if it would close a cycle. Both traces end with the same minimum total weight on this connected weighted graph.

Who it's for: Discrete math and algorithms courses connecting greedy MST constructions to the cut and cycle arguments; useful right after graph basics or alongside union–find lectures.

Key terms

Minimum spanning tree
Prim's algorithm
Kruskal's algorithm
Cut property
Cycle property
Union–find (DSU)
Complete graph
Euclidean weights

How it works

Random points in the plane, complete graph with Euclidean edge weights. Prim grows the MST from a chosen root by always adding the lightest edge crossing the cut between the tree and the rest. Kruskal scans all edges sorted by weight and uses union–find to accept an edge only if it connects two different components (otherwise it rejects a cycle). Step through both constructions; total MST weight should match between algorithms.

Frequently asked questions

Why is the graph complete—would a sparse graph be more realistic?: A complete Euclidean graph is a clean teaching model: every pair of sites could be wired in principle, and the MST picks the cheapest n−1 links that keep everything connected. Real networks are often sparse with missing edges; the same algorithms apply, but the dense case makes the Kruskal sort and the Prim “scan all crossing edges” story very explicit.
Does changing the Prim root change the final MST?: The set of edges in an MST is not always unique when weights tie, but every MST has the same total weight. Here ties are resolved deterministically, so you may see different edge sets for different roots if multiple MSTs exist, while the readout weights still match Kruskal.
What does the red dashed highlight mean in Kruskal mode?: That edge is the next candidate in sorted order, but both endpoints already lie in the same component, so adding it would create a cycle—Kruskal skips it.

Continue with similar topics in this category — or all 48 in Engineering.

View category →

NewSchool

Maze Generators + A* (Grid)

Launch Simulator

Perfect mazes on the same 40×28 cell lattice as the pathfinding lab: recursive backtracker, Wilson, Eller, or randomized Prim; then solve with Manhattan A* (4-neighbors). Paint walls or erase passages and move S/G.

NewSchool

A* / Dijkstra Pathfinding (Grid)

Launch Simulator

Interactive 40×28 grid pathfinder: A* (f=g+h), Dijkstra, or greedy best-first; Manhattan / octile / Euclidean heuristics, 4- vs 8-connectivity, paint walls + weighted cells, watch open / closed sets expand.

NewSchool

Finite State Machine

Launch Simulator

Traffic-light Moore machine: timed green–yellow–red cycle or manual step; state graph.

NewSchool

RRT Path Planner (grid)

Launch Simulator

Same 40×28 wall map as A*: random samples, nearest-neighbor steer, goal bias, collision-checked edges; grow an RRT and compare summary stats with one-click Manhattan A* baseline.

NewSchool

Two-Link Arm IK (2R)

Launch Simulator

Planar 2R manipulator: mouse goal, elbow-up / elbow-down inverse kinematics; joint angles live.

NewSchool

Beam Deflection: Unit Load Method

Launch Simulator

Simply supported Euler-Bernoulli beam with point load P and UDL w: closed-form deflection vs virtual-work unit-load integral.

Minimum Spanning Tree (Prim & Kruskal)

About this model

How it works

Frequently asked questions

Related simulators

Maze Generators + A* (Grid)

A* / Dijkstra Pathfinding (Grid)

Finite State Machine

RRT Path Planner (grid)

Two-Link Arm IK (2R)

Beam Deflection: Unit Load Method

Minimum Spanning Tree (Prim & Kruskal)

About this model

How it works

Frequently asked questions