Named after Robert C. Prim who discovered the algorithm in 1957. However, it was discovered that Vojtěch Jarník discovered it in 1930, so it is sometimes know as the Prim-Jarník algorithm.
The pseudo code below is a particularly slow implementation ($O(mn)$) of Prim’s algorithm. However, this simple implementation makes the algorithm easy to understand.
G = connected, undirected graph T = empty set (will contain edges in MST) cost = 0 find_smallest: G = input graph smallest = NULL // Loop through each edge where tail vertex is conquered and head vertex is not conqured for each vertex (v) in G where v is conquered: for each edge in v where edge->head is NOT conquered: if smallest is NULL OR edge->weight < smallest->weight: smallest = edge return smallest mark first vertex conquered e = find_smallest G while e != NULL: add e to T cost += e->weight mark e->head conquered edge = find_smallest G return T and cost
This version is more complex, but results in a considerably faster run time ($O((m+n)\log n)$)
- Heap contains vertices that have that have not yet been spanned
- Highest priority element in the heap is the next vertex to be conquered
G = connected, undirected graph T = empty set (will contain edges in MST) H = empty heap cost = 0 find_winning_edge: edges = edges to search return cheapest edge where head is conquered return NULL if no edges qualify mark first vertex conquered for v that is not conquered: winner = find_winning_edge v->edges if winner is NULL: score = infinity else score = winner->weight add v to H using score as the heap key value while H is not empty: v = extracted min from H mark v as conquered cost += v.score add winner to T (calculated in previous loop) for every edge in v where the head is not conquered: winner = cheapest edge in edge->head->edges if winner is NULL: score = infinity else score = winner->weight recacluate H for winner->head return T cost
Click here for build and run instructions