Prim's MST

O(E log V)

Prim's algorithm builds a minimum spanning tree — the cheapest set of edges connecting every node — by growing one tree outward. Starting from any node, it repeatedly adds the lowest-weight edge that connects the tree to a node not yet in it. With a priority queue it runs in O(E log V). Here edge weights are the distances between nodes, so drag them to reshape the MST.

Click empty space = vertex · click two vertices = edge · drag = moveStart: A
Input graph
Edit the input and press Play

How it works

  1. Start the tree with any single node.
  2. Look at every edge leaving the tree to an outside node.
  3. Add the cheapest such edge (and its node) to the tree.
  4. Repeat until every node is in the tree.

Pseudocode

1prim(graph, start):                 # O(E log V)2  tree ← { start }3  while a node is still outside the tree:4    pick the cheapest edge from the tree to an outside node5    add that node and edge to the tree