Prim's Algorithm

computation graph-theory algorithms

Definition

Prim's Algorithm

Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected network. It builds the tree one vertex at a time, starting from an arbitrary root vertex, at each step adding the cheapest possible connection from the tree to another vertex.

For dense graphs, where $|E|=\Theta (|V{|}^2)$, Prim’s algorithm typically performs better than Kruskal’s algorithm.

Logic and Implementation

1. Initialise a tree with a single vertex, chosen arbitrarily from the graph.
2. Maintain a priority queue containing all edges that connect the tree to vertices not yet in the tree.
3. Repeat until all vertices are in the tree:

• Extract the minimum-weight edge $(u,v)$ from the priority queue.
• If $v$ is not already in the tree, add the edge and the vertex $v$ to the tree.
• Update the priority queue with new edges from $v$ to vertices outside the tree.

Runtime

The time complexity of Prim’s algorithm depends on the data structure used for the priority queue:

Priority Queue Implementation	Time Complexity
Adjacency Matrix	$O(\Vert V{\Vert }^2)$
Binary Heap	$O(\Vert E\Vert \log \Vert V\Vert )$
Fibonacci Heap	$O(\Vert E\Vert +\Vert V\Vert \log \Vert V\Vert )$

The Fibonacci heap implementation is particularly efficient for dense graphs because the amortised cost of the $decrease-key$ operation is $O(1)$.