Minimum Spanning Tree
Connect everything as cheaply as possibleImagine laying cable between towns so that every town is connected and the total cost is as small as possible. The answer is a minimum spanning tree: V − 1 edges, no cycle, smallest total weight. Kruskal sorts all edges and takes the cheapest one that does not close a cycle; Prim grows a single tree, always adding the cheapest edge that leaves it.
- Spanning treeall V vertices, V − 1 edges, no cycle
- Minimumthe smallest total weight
- Kruskalcheapest edge that closes no cycle
- Primgrow one tree, cheapest edge out
- Current
- Looking at
- Done
- In the tree
- Rejected (cycle)
Ready
Edges are written A-B:4 (letters A–H, weights 1–99) · the graph must be connected · Keyboard: ← → step · Space play / pause · R reset
Every operation, in plain steps
These are exactly the steps the visualizer animates.
Cheapest way to connect everything
A SPANNING TREE of a connected, undirected, weighted graph is a set of V − 1 edges that connects all the vertices with no cycle. The MINIMUM spanning tree is the one with the smallest total weight. Both algorithms are GREEDY: they build the answer one cheapest-safe choice at a time. Kruskal looks at the edges (it needs a way to ask "are these two already connected?"), Prim looks at the vertices (it keeps key[v], the cheapest edge reaching v).
struct Edge { int u, v, w; };
// Kruskal: disjoint sets answer "already connected?"
int parent[V]; // parent[x] = x : x is the leader of its set
int find(int x) { // the leader of x's set
while (parent[x] != x) x = parent[x];
return x;
}
// Prim: the cheapest edge from the tree to every vertex
int key[V]; // key[v] = cheapest edge found so far
int parent[V]; // parent[v] = the tree vertex it joins
int inTree[V];
Kruskal's algorithm
- Sort all edges by weight, lightest first.
- Give every vertex its own set.
- Take the next edge: if its ends are in DIFFERENT sets, keep it and merge the sets.
- Same set = it would close a cycle: skip it. Stop at V − 1 edges.
Prim's algorithm
- Start the tree at any vertex (key 0); all other keys are ∞.
- Add the vertex outside the tree with the smallest key.
- For each of its neighbours outside the tree: if the edge is lighter than its key, update key and parent.
- Repeat until every vertex is in the tree.
Why does greedy work?
- Cut property: for any split of the vertices into two groups, the lightest edge across the split is in some MST.
- Prim uses the split "tree | everything else".
- Kruskal's lightest safe edge always crosses some split of two different sets.
- So taking the cheapest safe edge never ruins the optimum.
Detecting a cycle
- Kruskal keeps disjoint sets of vertices.
- find(u) = find(v) means u and v are already connected.
- Adding the edge u–v would then close a cycle.
- Different sets: no cycle, so union the two sets.
Kruskal or Prim?
- Sparse graph (few edges): Kruskal is simple and fast.
- Dense graph (many edges): Prim with an array is O(V²).
- Both give a tree of the same minimum weight.
- With equal weights the TREE may differ, but never the total.
Where it is used
- Laying cable, pipes or roads at least cost.
- Network design: connect all offices cheaply.
- Clustering: cut the heaviest MST edges to split data into groups.
- A building block for approximate travelling-salesman routes.
Pseudocode
Language-independent steps. The visualizer shows the same logic in C, Python and Java.
How fast is each operation?
V = vertices, E = edges. Kruskal is dominated by sorting the edges. Prim with a simple array scans for the minimum V times (O(V²)); with a binary heap it is O(E log V).
| Operation | Best | Average | Worst | Speed |
|---|---|---|---|---|
| Kruskal (sort + disjoint sets) | O(E log E) |
O(E log E) |
O(E log E) |
Grows with n |
| Prim (array) | O(V²) |
O(V²) |
O(V²) |
Grows with n |
| Prim (binary heap) | O(E log V) |
O(E log V) |
O(E log V) |
Grows with n |
| Find / Union (with path compression) | O(1) |
almost O(1) |
O(log V) |
Instant |
Kruskal vs Prim
| Kruskal | Prim | |
|---|---|---|
| Grows | A forest that merges into one tree | One tree from a start vertex |
| Works with | Edges (sorted by weight) | Vertices (key[v]) |
| Cycle check | Disjoint sets (find / union) | Never needed: only vertices outside the tree are added |
| Time | O(E log E) | O(V²) with an array, O(E log V) with a heap |
| Better for | Sparse graphs | Dense graphs |
| Disconnected graph | Gives a spanning FOREST | Only reaches the start's part |
Spanning tree facts
| Fact | Because |
|---|---|
| Every spanning tree has exactly V − 1 edges | Fewer edges leave a vertex out; more edges close a cycle |
| A connected graph has at least one spanning tree | Keep removing an edge from a cycle until none is left |
| If all weights are different, the MST is unique | There is never a tie to break differently |
| The MST is NOT the shortest path tree | It minimises the total weight, not the distance from one vertex |
Check your understanding
Answer each question — you will see the explanation straight away.
A connected graph has 9 vertices. How many edges does any spanning tree of it have?
A spanning tree always has V − 1 = 8 edges: fewer would leave a vertex out, more would close a cycle.
In Kruskal's algorithm, when is an edge rejected?
If find(u) = find(v), u and v are already connected, so adding the edge would create a cycle.
In which order does Kruskal's algorithm look at the edges?
Kruskal sorts the edges by weight and always considers the cheapest remaining edge.
In Prim's algorithm, what does key[v] store?
key[v] is the cheapest known way to attach v to the tree. Prim always adds the outside vertex with the smallest key.
Prim and Kruskal are both run on the same connected graph. What is certain about their results?
Both are correct, so both find a minimum spanning tree: the same minimum weight (with ties the edges may differ).
Which algorithm is usually the better choice for a graph with very FEW edges?
Kruskal costs O(E log E), which is small when E is small. Prim with an array always costs O(V²).
Kruskal's algorithm can stop as soon as…
A spanning tree has exactly V − 1 edges, so after taking that many the remaining edges can only close cycles.
The minimum spanning tree gives the shortest path from the start vertex to every other vertex.
The MST connects everything as cheaply as possible overall. A route inside it can be much longer than the direct shortest path — that is Dijkstra's job.
Graphs quiz
Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.