Visualize & Master
Algorithms & Data Structures
Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.
About A Minimum Spanning Tree (MST) of a connected weighted undirected graph is a spanning tree with the minimum total edge weight
A Minimum Spanning Tree (MST) of a connected weighted undirected graph is a spanning tree with the minimum total edge weight.
It connects all V vertices using exactly V-1 edges.
Two classic algorithms — Prim's and Kruskal's — both use greedy strategies but differ in approach.
How It Works
**Prim's** grows the MST one vertex at a time: start from any vertex, repeatedly add the cheapest edge that connects a visited vertex to an unvisited one.
**Kruskal's** grows the MST one edge at a time: sort all edges by weight, then greedily add edges that don't form a cycle (tracked using a Union-Find / Disjoint Set Union data structure).
Both algorithms are guaranteed to produce the same MST weight.
Time & Space Complexities
| Operation | Time | Space |
|---|---|---|
| Prim's Time (binary heap) | O((V + E) log V) | O(V) |
| Kruskal's Time | O(E log E) | O(V) |
| Union-Find find/union | O(α(V)) ≈ O(1) | O(V) |
| MST edges | Always V - 1 edges | — |
| Unique MST? | Yes if all weights distinct | — |
Best Use Cases
- Network infrastructure — minimum cable to connect all buildings
- Clustering algorithms (remove MST edges for k clusters)
- Circuit design — connecting components with minimum wire
- Approximation algorithms for the Travelling Salesman Problem
- Image segmentation in computer vision
Worked Example
Kruskal on a 6-node weighted graph (MST weight 11)
Input: A–B(4), A–C(2), A–D(6), B–D(3), B–E(5), C–F(3), D–C(1), D–F(4), E–D(2), E–F(6)- 1 Sort edges by weight: D–C(1), A–C(2), E–D(2), B–D(3), C–F(3), then heavier edges.
- 2 Add D–C(1): no cycle, union {C, D}.
- 3 Add A–C(2): union {A, C, D}; add E–D(2): union {A, C, D, E}.
- 4 Add B–D(3): union all of A–E; add C–F(3): union F into the set — now 5 edges, one per component.
- 5 Stop at V−1 = 5 edges. A–B(4) and D–F(4) would be rejected (they would close cycles).
- 6 Total weight: 1 + 2 + 2 + 3 + 3 = 11. Prim grows from A with the same edges and reaches the same total.
Pseudocode
function Kruskal(graph):
sort edges by weight ascending
DSU = new UnionFind(V)
MST = []
for each edge (u, v, w) in sorted order:
if find(u) != find(v):
MST.add(edge)
union(u, v)
if |MST| == V - 1: break
return MST function Prim(graph, start):
key[start] = 0; key[v] = ∞ for all others
parent[v] = null for all v
inMST = {}
while |inMST| < V:
u = vertex not in MST with min key
inMST.add(u)
for each edge (u, v, w):
if v not in MST and w < key[v]:
key[v] = w; parent[v] = u
return parent (encodes MST edges) BFS — Breadth-First Search
Queue
Distances
| Node | Dist | Parent |
|---|
Result Order
SCC Groups
Distance Matrix
Select an algorithm and press Play to begin.