Minimum Spanning Tree
Find the subset of edges that connects all vertices with minimum total weight.
A
B
C
D
E
F
Total Weight: 0
Status: Click Run to Start
Speed
1function prim(start):
2 visited = {start}
3 pq = getEdges(start)
4 mst = []
5
6 while pq not empty:
7 edge = pq.extractMin()
8 if edge.to in visited: continue
9
10 visited.add(edge.to)
11 mst.add(edge)
12 pq.add(getEdges(edge.to))
Prim's builds graph node by node, always picking the smallest edge connected to the growing tree.