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