Minimum Spanning Tree (Kruskal & Prim)

Overview

The Minimum Spanning Tree visualizer demonstrates Kruskal’s and Prim’s algorithms for finding the minimum spanning tree of a weighted graph. A spanning tree connects all vertices with the minimum total edge weight and no cycles. Watch as Kruskal’s algorithm sorts edges and adds them greedily while avoiding cycles, and see how Prim’s algorithm grows the tree from a starting vertex. Essential for understanding network design, clustering, and approximation algorithms.

Open in new tab

Tips

• Both algorithms find the same minimum spanning tree (though edge selection order differs)
• Kruskal’s sorts all edges by weight and adds them if they don’t create a cycle (uses Union-Find)
• Prim’s grows the tree one vertex at a time, always choosing the minimum weight edge
• The total weight of the MST is shown - this is minimized across all possible spanning trees
• Kruskal is better for sparse graphs, Prim is better for dense graphs
• MSTs are used in network design, clustering, and as a subroutine in approximation algorithms
• Watch the edge selection order - both algorithms are greedy but use different strategies
• The visualization highlights selected edges in green as they’re added to the MST