Connect every vertex using the least total edge weight. Kruskal sorts edges globally; Prim grows outward from one node. Both are greedy, both are optimal — and they often pick different edges.
Controls
Edges by weight
Building the Tree
step 0
Insight
An MST connects all V vertices with exactly V−1 edges and no cycles, at minimum total weight.
edges chosen0
needed–
total weight0
rejected0
Complexity
KruskalO(E log E)
Prim (heap)O(E log V)
SpaceO(V+E)
Overview
A spanning tree connects every vertex of a graph using exactly V−1 edges and no cycles. The minimum spanning tree is the one with the smallest total edge weight — the cheapest way to keep everything connected.
Start here
The MST has practical applications wherever you need to connect things at minimum cost: laying cable between buildings, connecting computers in a network, or building roads between cities.
Kruskal: Sort Globally, Add Safely
Sort every edge by weight, cheapest first.
Take each in turn. Add it if its endpoints are in different components; skip it if they are already connected, since that would create a cycle.
Stop after V−1 edges.
The connectivity check is exactly what union-find is for — a near-constant-time "same group?" query. Kruskal is the headline application of that structure.
Notice that Kruskal's partial result is often a forest of disconnected fragments that only merge into one tree at the end.
Prim: Grow One Tree Outward
Start at any vertex.
Repeatedly add the cheapest edge that connects the tree to a vertex not yet in it.
Stop when every vertex is included.
Prim keeps a single connected tree at all times, which is why it needs a priority queue of frontier edges rather than union-find. With a binary heap it runs in O(E log V).
Why Greedy Is Provably Correct Here: The Cut Property
Split the vertices into any two groups. The cheapest edge crossing that divide must be in some MST. That is the cut property, and both algorithms are just different ways of applying it.
Prim applies it to the cut between "in the tree" and "not in the tree". Kruskal applies it implicitly — when it adds the cheapest edge joining two components, that edge crosses the cut between them.
This is why greedy never has to backtrack, unlike the coin-change failure in the greedy module.
Which One to Use
Kruskal suits sparse graphs — the cost is dominated by sorting E edges. It also works naturally when edges arrive as a list.
Prim suits dense graphs, where E approaches V², because it never sorts everything.
If edge weights are all distinct the MST is unique, so both produce identical trees. With ties they may choose different edges — but the total weight always matches.
Real Uses
Laying cable, pipe or road networks at minimum cost; clustering (remove the k−1 most expensive MST edges to get k clusters); approximation algorithms for the travelling salesman problem; and network design generally.
The cheapest way to connect everything
Given a weighted undirected graph, a spanning tree connects all vertices using exactly V−1 edges and no cycles. A minimum spanning tree is the one with the lowest total weight.
The practical question it answers: what is the cheapest set of connections that leaves nothing isolated? Laying cable, building a road network, connecting offices — wherever connectivity is required and redundancy is not.
Two properties are worth stating, because they are what the algorithms rely on:
Exactly V−1 edges. Fewer leaves the graph disconnected; more creates a cycle, and the heaviest edge in a cycle can always be removed.
The cut property. For any way of splitting the vertices into two groups, the lightest edge crossing the split is in some MST. That single fact is what makes greedy algorithms correct here.
The MST is not necessarily unique — equal edge weights allow several — but the total weight is.
Things to try with Minimum Spanning Tree
Run Kruskal. Watch it consider edges in weight order and reject any that would close a cycle.
Note the disconnected fragments mid-run — Kruskal builds a forest that only becomes one tree at the very end.
Continue with union-find, which builds on this idea.
Run it in Python
Kruskal and Prim on the same weighted graph. They pick edges in completely different orders and arrive at the same total weight — which is the property worth seeing rather than being told.
mst.pyPython 3
# Minimum spanning tree, twice: Kruskal (sort edges) and Prim (grow a tree).
import heapq
edges = [("A", "B", 4), ("A", "C", 8), ("B", "C", 11), ("B", "D", 8),
("C", "E", 7), ("D", "E", 2), ("D", "F", 4), ("E", "F", 9),
("C", "F", 1)]
nodes = sorted({n for u, v, _ in edges for n in (u, v)})
# --- Kruskal: cheapest edge first, skip any that closes a cycle ---------
def kruskal():
parent = {n: n for n in nodes}
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path compression
x = parent[x]
return x
tree, total = [], 0
for u, v, w in sorted(edges, key=lambda e: e[2]):
ru, rv = find(u), find(v)
if ru == rv:
print(f" skip {u}-{v} ({w}) - would close a cycle")
continue
parent[ru] = rv
tree.append((u, v, w))
total += w
print(f" take {u}-{v} ({w})")
return tree, total
# --- Prim: grow one tree, always out along its cheapest edge ------------
def prim(start):
adj = {n: [] for n in nodes}
for u, v, w in edges:
adj[u].append((w, v))
adj[v].append((w, u))
seen = {start}
heap = list(adj[start])
heapq.heapify(heap)
tree, total = [], 0
while heap and len(seen) < len(nodes):
w, node = heapq.heappop(heap)
if node in seen:
continue
seen.add(node)
tree.append((node, w))
total += w
print(f" take {node} ({w})")
for nxt in adj[node]:
if nxt[1] not in seen:
heapq.heappush(heap, nxt)
return tree, total
print("Kruskal:")
k_tree, k_total = kruskal()
print("Prim from A:")
p_tree, p_total = prim("A")
print()
print("Kruskal edges :", [f"{u}-{v}" for u, v, _ in k_tree], "total", k_total)
print("Prim weights :", [w for _, w in p_tree], "total", p_total)
print(f"{len(nodes)} nodes -> {len(k_tree)} edges. A spanning tree always has V-1.")
Output
How the code works
sorted(edges, key=lambda e: e[2])Kruskal's entire strategy: cheapest first, globally, ignoring where the edges are. The sort is also its dominant cost — O(E log E).
if ru == rv: continueBoth ends already connected means this edge adds nothing but a cycle. Union-find answers that in near-constant time; without it the check would need a traversal per edge.
heap = list(adj[start])Prim starts from one node and only ever considers edges leaving the tree it has grown. It never sees most of the graph at once, which is the opposite of Kruskal's global sort.
if node in seen: continueSame lazy deletion as Dijkstra — and Prim really is Dijkstra with the priority changed from “distance from the start” to “weight of this one edge”.
len(k_tree) == len(nodes) - 1Any spanning tree of V nodes has exactly V − 1 edges. Both algorithms hit that count and the same total, though the edge sets can differ when weights tie.
Change one thing
Print the two edge sets side by side. On this graph they match; make two edges equal in weight and they can diverge while the totals stay equal.
Delete edge C-F. Kruskal's very first choice changes and the whole tree reshapes.
Remove an edge so the graph is disconnected. Kruskal returns fewer than V − 1 edges — a spanning forest, which is often what you actually wanted.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Predict, then reveal
About to run: Run Kruskal. Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
A spanning tree of a graph with V nodes always has:
Exactly enough to connect everything with no cycle. Both Kruskal and Prim stop at that count in the program.
The difference between Kruskal and Prim is that Kruskal:
Kruskal works from a global sort and needs union-find to reject cycles; Prim grows locally from one node with a priority queue.
Kruskal uses union-find to:
Both endpoints already in the same component means the edge adds only a cycle. Without union-find that check would need a traversal per edge.
Cheat sheet
Minimum Spanning Tree
Connect every vertex at minimum total cost with Kruskal's edge-sorting and Prim's vertex-growing approaches side by side.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.