Graph Theory37 sections · 1633 units
Open in Course

Prim's Algorithm - Idea

(Grow tree from one node)

Prim's algorithm builds the MST by growing a single tree from a starting node. Start with any node. Repeatedly add the cheapest edge that connects a node inside the tree to a node outside. Think of it as expanding a blob.

The blob starts as one node. At each step, you grab the nearest node outside the blob and pull it in. The difference from Kruskal: Prim grows one connected component. Kruskal manages a forest of components.