Advanced · Module 18 · Lesson 4 of 4
Prim's algorithm
Prim's algorithm grows one tree from a starting vertex, each time adding the cheapest edge that leaves it. It looks like Dijkstra's algorithm with a different priority, and its array version is the best choice for dense graphs.
By the end you can
- Run Prim's algorithm, keeping each outside vertex's cheapest edge into the tree
- Choose between the O(V²) array version and the O(E log V) heap version
- Compare Prim with Kruskal and with Dijkstra
Builds on Kruskal's algorithm, Dijkstra's algorithm.
01 · A question first
A thousand points on a map, where linking any two costs their distance: half a million possible edges. Kruskal would list and sort them all. Prim's algorithm never lists a single edge in advance, yet it builds the same cheapest network in about a million simple steps. How?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Growing one tree
- Why it is correct
- Two implementations
- Prim and Dijkstra
- Worked example: points on a plane
- Choosing between Prim and Kruskal
- Beyond these two
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
03 · Practice
Something wrong with this lesson? Report a problem