Vertex growth process for MST formation emphasizing candidate edge relaxation.
Easy Explanation
Prim grows a minimum spanning tree from one node by repeatedly taking the cheapest edge to a new node.
Nodes / Edges
0 / 0
Visited
0
Total Weight
0
Result
Processing
Press Play or Step to start execution.
Progress
candidates 0, locked 0, components 0
Current Node
n/a
Selected Edges
n/a
function primMst(nodeCount, edges, start):
inTree <- set with start
mst <- []
totalWeight <- 0
while inTree has not all nodes:
bestEdge <- null
for each edge (u, v, w):
if u inTree and v not inTree:
consider (u, v, w)
else if v inTree and u not inTree:
consider (v, u, w)
keep the minimum candidate edge by weight
if bestEdge is null:
break // disconnected component finished
add bestEdge.to to inTree
append bestEdge to mst
totalWeight <- totalWeight + bestEdge.weight
return { mst, totalWeight }