Sign in to watch this lesson
Algorithms - Graphs II · 4:28
Prim's Minimum Spanning Tree
Prim's algorithm grows a single tree outward from one vertex, always adding the shortest edge that leaves it; on twelve desks of a floor plan, the dashed 'cheapest link' of every outside desk swings and shortens as the tree approaches, for a total of about 50.14 m. Its key is the edge's length, not the route's (mixing it up with Dijkstra builds a shortest-path tree), and it comes in a dense O(n^2) version that never stores the edges and a heap version for sparse graphs, measured against Kruskal on this Mac.
You will learn
- Run Prim's algorithm by hand, keeping each outside vertex's cheapest link into the tree, and justify each step with the cut property
- Implement the dense O(n^2) version with O(n) memory, computing edge lengths on the fly (squared integers, one sqrt per tree edge)
- Implement the heap version in O(m log n) with lazy deletion
- Explain the difference between Prim's key and Dijkstra's, and choose between dense Prim, heap Prim and Kruskal from the graph's density