Prim's algorithm

Prim's algorithm is a greedy algorithm used to find the Minimum Spanning Tree in a graph.

It works well for dense graphs.


Algorithm

1. Initialize the tree: chose the root node, which is a single vertex chosen arbitrarily from the graph.
2. Grow the tree by one edge, by choosing one with the minimum weight (e.g. distance).
3. Repeat step 2, until all vertices are in the tree.

Complexity

Prim algorithm complexity can change depending of the data structure used.

Operation	Array	List	Tree	Heap	Fibonacci heap
Insert	$O(1)$	$O(1)$	$O(\log n)$	$O(\log n)$	$O(1)$
Access minimum	$O(n)$	$O(n)$	$O(\log n)$	$O(1)$	$O(1)$
Delete minimum	$O(n)$	$O(n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$ (amorti)
Decreases key	$O(1)$	$O(1)$	$O(\log n)$	$O(\log n)$	$O(1)$ (amorti)

Resources

• Prim's algorithm visualization – David Galles