Example — Running Prim’s Algorithm from Vertex A
We now execute Prim’s algorithm on a weighted graph. The rule is always the same: look at the edges leaving the current tree and choose the lightest valid one.
We will start at vertex A. At the beginning, the tree contains only that vertex.
Step 1 — Start at A
The tree begins with vertex A only.
The edges leaving A are: A–C = 1 and A–B = 2.
The smallest one is A–C = 1, so we add edge A–C and vertex C.
Step 2 — Expand from {A, C}
Now the current tree contains A and C.
We examine all edges leaving this tree: A–B = 2, C–E = 4, C–D = 6, and C–F = 8.
The lightest available edge is A–B = 2, so we add B to the tree.
Step 3 — Expand from {A, B, C}
The candidate edges are now: B–D = 3, C–E = 4, C–D = 6, and C–F = 8.
The smallest one is B–D = 3. So we add edge B–D and include vertex D.
Notice how Prim does not sort every edge globally. It only cares about the boundary of the current tree.
Step 4 — Add E
The tree currently contains A, B, C, D. The edges leaving it include C–E = 4, D–F = 5, D–E = 9, and C–F = 8.
The smallest edge is C–E = 4, so we add vertex E.
Step 5 — Add F
Only vertex F remains outside the tree.
The edges connecting the current tree to F are D–F = 5 and C–F = 8.
The lightest one is D–F = 5, so we add that edge and complete the spanning tree.
Final Result
The minimum spanning tree found by Prim’s algorithm is:
A–C = 1, A–B = 2, B–D = 3, C–E = 4, D–F = 5.
The total weight is: 1 + 2 + 3 + 4 + 5 = 15.
The result is a tree because it connects all vertices and uses exactly n − 1 edges with no cycles.
Key Insight from Part 2
Prim’s algorithm always builds one connected structure.
At each step, it looks only at the frontier of the current tree and picks the cheapest edge that expands it.
This is why Prim feels different from Kruskal: Prim grows one tree, while Kruskal merges components.