# Prim's Minimum Spanning Tree

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.

## Asymptotic Complexity

$O((m+n)\log n)$

## Pseudo Code

### Naive Implementation

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:
cost += e->weight
edge = find_smallest G

return T and cost


### Heap-Based Implementation

This version is more complex, but results in a considerably faster run time ($O((m+n)\log n)$)

Invariants:

• 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