AlgoVerse

Prim's algorithm

Grow the minimum spanning tree from one node: each time, add the lightest edge that joins a new node to the tree.

Prim's algorithm also builds a minimum spanning tree, but unlike Kruskal it grows it from one node. At every moment there is one tree (in_tree). Of all the edges that join a node in the tree to a node outside it, take the lightest and add the new node to the tree.

Read the full explanation ↓
Input:
V=9 · E=14 · src=APDF export

The same nine-node graph as in the Kruskal example, this time grown from A; the tree weight is again 37.

  1. from heapq import heappop, heappush
  3. INF = float("inf")
  6. def prim(graph, src):
  7. key = {v: INF for v in graph}
  8. parent = {v: None for v in graph}
  9. key[src] = 0
  10. pq = [(0, src)]
  11. in_tree = set()
  12. while pq:
  13. k, u = heappop(pq)
  14. if u in in_tree:
  15. continue
  16. in_tree.add(u)
  17. for v, w in graph[u]:
  18. if v not in in_tree:
  19. if w < key[v]:
  20. key[v] = w
  21. parent[v] = u
  22. heappush(pq, (w, v))
  23. return parent, key

Invariant: The parent edges between the nodes in in_tree are always part of some minimum spanning tree.

Start

48118247149102617ABCDEFGHI
  • Final
  • Current node (u)
  • Minimum spanning tree so far
  • Edge being checked

Priority queue pq

empty

Local variables

src'A'

Orange = changed in this step

graph dict
  • 'A': [('B', 4), ('H', 8)]
  • 'B': [('A', 4), ('H', 11), ('C', 8)]
  • 'C': [('B', 8), ('I', 2), ('F', 4), ('D', 7)]
  • 'D': [('C', 7), ('F', 14), ('E', 9)]
  • 'E': [('D', 9), ('F', 10)]
  • 'F': [('C', 4), ('D', 14), ('E', 10), ('G', 2)]
  • 'G': [('F', 2), ('I', 6), ('H', 1)]
  • 'H': [('A', 8), ('B', 11), ('G', 1), ('I', 7)]
  • 'I': [('C', 2), ('G', 6), ('H', 7)]

Call stack

  1. prim()line 6
Step 1 of 175
Black = pop · Orange = key stepcompare: 0/14 · push: 0/13 · pop: 0/13 · add: 0/9 · update: 0/12 · skip: 0/4

    How the work grows with input size

    Average of 5 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • comparisons
    • update
    • current input (n=9)
    0204060481216202428n = number of nodescomparisonsupdate
    Show as a table
    ncomparisonsupdate
    45.24.4
    813.811
    1220.816
    162822.8
    2035.428.4
    2437.232.4
    2847.240
    Explanation

    The idea

    Prim's algorithm also builds a minimum spanning tree, but unlike Kruskal it grows it from one node. At every moment there is one tree (in_tree). Of all the edges that join a node in the tree to a node outside it, take the lightest and add the new node to the tree.

    key and the priority queue

    For each node outside the tree, key[v] is the weight of the lightest edge known so far that joins v to the tree. The node with the smallest key is found with a priority queue, exactly as in Dijkstra:

    1. The node with the smallest key comes out of the queue. If it is already in the tree, it is skipped.
    2. It joins the tree.
    3. For each neighbour v outside the tree: if edge u — v is lighter than key[v], update key[v] and parent[v] and push v with its new key.

    How it differs from Dijkstra

    The two algorithms have the same shape; only the test differs. Dijkstra asks dist[u] + w < dist[v] (the whole path length from the source), Prim only w < key[v] (the weight of that one edge). That is why Dijkstra's tree gives shortest paths and Prim's tree the smallest total weight.

    Cost

    With a binary-heap priority queue, O((V + E) log V).

    What to watch in the trace

    • The number next to each node is its key; the blue edges (from parent) are the tree so far.
    • On the "complete graph" input the priority queue fills with stale (struck-through) entries.
    • Compare the final tree with Kruskal's result on the same graph ("textbook-style example"): both weigh 37.