Prim's Algorithm
A greedy algorithm that finds a minimum spanning tree for a weighted undirected graph by growing the tree one edge at a time.
Prim's Algorithm Visualization
How to use: Click empty space to add a vertex. Click two vertices to add an undirected weighted edge. Drag to reposition. Right-click to delete.
SlowFast
🔊 Sound
Ready
● Considering edge● Relaxed / Frontier● Added to MST● In MST
Priority Queue (min-key)
empty
Key Values
MST Edges
—
Complexity
Time Complexity:
O(E log V)Space Complexity:
O(V)Pseudocode
function prim(graph, start):
visited = set()
minHeap = priority queue
add (0, start) to minHeap
while minHeap not empty:
weight, node = extract min
if node not in visited:
add node to visited
for neighbor, edgeWeight in graph[node]:
if neighbor not visited:
add (edgeWeight, neighbor) to minHeap