Prim's Algorithm

algorithms graph-theory

Definition

Prim's Algorithm

Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a undirected network.

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

Runtime

• If a priority queue with classic heap implementation is used, then the total time complexity is $O(|E|\log |V|)$.
• If a priority queue with Fibonacci heap implementation is used, then the total time complexity reduced to $O(|E|+|V|\log |V|)$.