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)

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.

Other simulators in this category — or see all 33.

View category →

NewSchool

Maze Generators + A* (Grid)

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.

Launch Simulator

NewSchool

RRT Path Planner (grid)

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.

Launch Simulator

NewSchool

Differential Drive Odometry

ω_L, ω_R → v, ω with two-wheel kinematics; integrate pose and watch dead-reckoning drift from biased wheel radii / track and noisy rate readings.

Launch Simulator

NewUniversity / research

Holonomic 2D Hovercraft MPC (MPPI)

Planar double integrator with ‖u‖₂ thrust cap: sampling-based MPPI steers to a draggable goal while soft-penalizing circular obstacles — rollout fan and best predicted path drawn live.

Launch Simulator

NewUniversity / research

3-Link 3D Arm Inverse Kinematics (CCD)

Continuation of two-link-arm-ik into 3D: 3 revolute joints (yaw + 2 pitches) solved with constrained Cyclic Coordinate Descent. Drag target in 3D or follow a helix / lemniscate / figure-8 trajectory.

Launch Simulator

NewUniversity / research

Bicycle Model & Stanley Controller

Kinematic bicycle (rear-axle): δ = θ_e + atan2(k_e·e, v) Stanley path-following law. Pick oval, race-track, lemniscate, sine-road or S-curve and tune k_e, v, L; live cross-track e(t) and steering δ(t).

Launch Simulator

Minimum Spanning Tree (Prim & Kruskal)

How it works

Frequently asked questions

More from Engineering

Maze Generators + A* (Grid)

RRT Path Planner (grid)

Differential Drive Odometry

Holonomic 2D Hovercraft MPC (MPPI)

3-Link 3D Arm Inverse Kinematics (CCD)

Bicycle Model & Stanley Controller

Minimum Spanning Tree (Prim & Kruskal)

How it works

Frequently asked questions