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.

MST-PRIM

Input: A weighted, undirected graph G=(V, E, w)

Output: A minimum spanning tree T.

T={}

Let r be an arbitrarily chosen vertex from V.

U = {r}

WHILE | U| < n

DO

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}

Analysis

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.