Prim-Jarnik's algorithm for extracting Minimum Spanning Tree (MST)

This algorithm comes under the greedy method, which means that the objects are chosen to join a growing collection by iteratively picking an object that minimizes some cost function.

Now, taking account of the above mentioned greedy method, the Prim-Jarnik's algorithm is similar to the Dijkstra's shortest-path algorithm to grow the Minimum Spanning Tree (MST) from a single cluster starting with a randomly chosen single root vertex.

The Prim-Jarnik's algorithm can be broken down as follows:
Step 1: Define the starting "cloud" of vertices [C] by selecting some random vertex [v] initially
Step 2: Iteratively choose a min-weight edge [e=(v,u)], thereby connecting a vertex [v] in the cloud [C] to a vertex [u] outside of [C]. After choosing [e] the vertex [u] is brought into the cloud [C] continuously until a spanning tree emerges.


Pseudo-code of the Prim-Jarnik's algorithm
// Prim-Jarnik(G) [Time complexity = O(m * log * n)]
// Input: A weighted connected graph [G] with n number of vertices & m number of edges
// Output: A minimum spanning tree [T] for [G]

// Pick a root vertex [v] of [G]
D[v] <- 0

// All vertices connected to the root vertex, hence it necessary to define the cost function.
// The cost function "D[u] = +infinity" when vertex [u] doesn't connect to vertex [v].
for each vertex u != v do
D[u] <- +infinity

// Initialise the MST
T <- null

// Initialise a priority queue Q with an entry ((u,null),D[u]) for each vertex [u],
// where (u,null) is the element & D[u] in the key
while Q is not empty do
(u,e) <- Q.removeMin()
Add vertex u and edge e to T

// Perform the relaxation procedure on the edge of the vertex [z] adjacent to [u]
For each vertex z adjacent to u such that z is in Q do
if W((u,z)) <>
D[z] <- W((u,z))
Change to (z,(u,z)) the element of vertex z in Q
Change to D[z] the key of vertex z in Q
return the tree T