Minimum Spanning Trees: Prim's Algorithm
You'll learn how to build a minimum spanning tree by starting from one vertex and greedily adding the cheapest edge that connects to a new vertex.
The Core Idea
Prim's algorithm constructs a minimum spanning tree (MST) by growing it one edge at a time. Unlike Kruskal's algorithm, which considers all edges globally, Prim's algorithm works more like a spreading ink stain: you start with a single vertex, then repeatedly add the minimum-weight edge that connects your growing tree to a new, unvisited vertex.
Think of it like building a transportation network outward from a central city. At each step, you choose the cheapest road that connects a city already in your network to a new city outside it.
How Prim's Algorithm Works
- Initialize: Pick any starting vertex and add it to the MST.
- Grow: Look at all edges connecting vertices inside the MST to vertices outside the MST.
- Choose minimum: Select the edge with the smallest weight among those crossing the boundary.
- Add: Include this edge and its new vertex in the MST.
- Repeat: Continue until all vertices are included.
Example Walkthrough
Suppose you have vertices A, B, C, D with edges:
- A–B: weight 2
- A–C: weight 3
- B–C: weight 1
- B–D: weight 4
- C–D: weight 2
Starting at vertex A:
- MST = {A}. Edges crossing: A–B(2), A–C(3). Choose A–B.
- MST = {A, B}. Edges crossing: B–C(1), A–C(3), B–D(4). Choose B–C.
- MST = {A, B, C}. Edges crossing: C–D(2), B–D(4). Choose C–D.
- All vertices included. MST weight = 2 + 1 + 2 = 5.
Key Takeaway: Prim's algorithm builds an MST by always adding the cheapest edge that connects a new vertex to the growing tree, ensuring optimal total weight.