Prim's algorithm

Prim's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm was discovered in 1930 by mathematician Vojtěch Jarník and later independently by computer scientist Robert C. Prim in 1957 and rediscovered by Dijkstra in 1959. Therefore it is sometimes called the DJP algorithm or Jarnik algorithm

A simple implementation using an adjacency matrix graph representation and searching an array of weights to find the minimum weight edge to add requires O(V^2) running time. Using a simple binary heap data structure and an adjacency list representation, Prim's algorithm can be shown to run in time which is O(Elog V) where E is the number of edges and V is the number of vertices. Using a more sophisticated Fibonacci heap, this can be brought down to O(E + Vlog V), which is significantly faster when the graph is dense enough that E is Ω(Vlog V).

The algorithm continuously increases the size of a tree starting with a single vertex until it spans all the vertices.
Input: A connected weighted graph G(V,E)
Initialize: V' = {x}, where x is an arbitrary node from V, E'= {}
repeat until V'=V:
Choose edge (u,v) from E with minimal weight such that u is in V' and v is not in V' (if there are multiple edges with the same weight, choose arbitrarily)
Add v to V', add (u,v) to E'
Output: G(V',E') is the minimal spanning tree