Graph AlgosGraph Algorithms

Prim's Algorithm

Minimum spanning tree by growing one tree from a start node, always adding the cheapest edge that crosses from the tree to a new node.

Learn Prim's Algorithm →
42518103263A0B∞C∞D∞E∞F∞G∞
key / parent
nodekeyparent
A0—
B∞—
C∞—
D∞—
E∞—
F∞—
G∞—
1/19Start Prim at A with key 0; every other key is ∞. key[v] is the cheapest known edge connecting v to the growing tree.
Node just addedCandidate (has finite key)In treeBest edge into a candidateMST edge
PseudocodeLearn Prim's Algorithm →
1key = {v: ∞}; key[start] = 0; inTree = {}
2while some node is not in tree:
3  u = node not in tree with minimum key
4  inTree.add(u); add edge (parent[u], u) to MST
5  for (v, w) in neighbors(u):
6    if v not in tree and w < key[v]:
7      key[v] = w; parent[v] = u
Variables
startA
Complexity
best O(E log V)
avg O(E log V)
worst O(E log V)
space O(V + E)
Speed