Prim's Algorithm

This algorithm was first propsed by Jarnik, but typically attributed to Prim. it starts from an arbitrary vertex (root) and at each stage, add a new branch (edge) to the tree already constructed; the algorithm halts when all the vertices in the graph have been reached. This strategy is greedy in the sense that at each step the partial spanning tree is augmented with an edge that is the smallest among all possible adjacent edges.


Input: A weighted, undirected graph G=(V, E, w)
Output: A minimum spanning tree T.

Let r be an arbitrarily chosen vertex from V.
U = {r}
WHILE | U| < n
Find u in U and v in V-U such that the edge (u, v) is a smallest edge between U-V.
T = TU{(u, v)}
U= UU{v}

The algorithm spends most of its time in finding the smallest edge. So, time of the algorithm basically depends on how  do we search this edge.
Straightforward method
Just find the smallest edge by searching the adjacency list of the vertices in V. In this case, each iteration costs O(m) time, yielding a total running time of O(mn).

Binary heap
By using binary heaps, the algorithm runs in O(m log n).

Fibonacci heap
By using Fibonacci heaps, the algorithm runs in O(m + n log n) time.