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:
    add e to T
    cost += e->weight
    mark e->head conquered
    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

        recacluate H for winner->head

return T cost

Source Code

Full Repo

Relevant Files:

Click here for build and run instructions