Prim's Algorithm: Overview
What You'll Learn
You'll learn how Prim's algorithm builds a minimum spanning tree by greedily growing it one edge at a time from a starting vertex.
The Core Idea
Prim's algorithm takes a completely different approach from Kruskal's. Instead of sorting all edges globally and merging components, Prim's grows a single tree continuously from a starting vertex.
Think of it like growing a crystal from a seed: you start with one vertex, then repeatedly attach the cheapest edge that connects your growing tree to a new vertex outside the tree. At each step, you're asking: "Of all edges touching my current tree, which one has the smallest weight and leads to an unvisited vertex?"
How It Works
- Start with any vertex as your initial tree (containing just that one vertex)
- Repeat until all vertices are in the tree:
- Look at all edges connecting the tree to vertices not yet in the tree
- Pick the edge with minimum weight
- Add that edge and its new vertex to the tree
This greedy choice is always safe because of the cut property you learned earlier: the minimum-weight edge crossing a cut (between tree vertices and non-tree vertices) must be in some MST.
Analogy
Imagine building a subway system starting from city hall. Each day, you extend rails to the nearest unconnected city using the cheapest available route from your existing network. You never jump to a disconnected city—you always grow continuously.
Key Takeaway: Prim's algorithm grows a single MST from a starting vertex by repeatedly adding the minimum-weight edge that connects the tree to a new vertex, relying on the cut property for correctness.