Prim's algorithm is a greedy algorithm used to find a minimum spanning tree (MST)
for a weighted undirected graph. This means it finds a subset of the edges that
forms a tree that includes every node, where the total weight of all the edges
in the tree is minimized. The algorithm operates by building this tree one node
at a time, starting from an arbitrary node, and at each step adding the cheapest
possible connection from the tree to another node. Think of it like a greedy BFS.
Algorithm Procedure and Visualization
Steps:
Initialize a minimum spanning tree with a single node, chosen arbitrarily from the graph.
Maintain a set of vertices already included in the MST (let's call it MSTSet).
Maintain a set of candidate edges connecting vertices in MSTSet to vertices outside MSTSet. Use a priority queue for efficiency.
Repeat the following steps until all vertices are included in the MST:
Select the edge with the minimum weight from the candidate edges that connects a node in MSTSet to a node not in MSTSet.
Add the selected edge and the newly reached node to the MSTSet.
Update the candidate edges: Add new edges from the newly added node to vertices still outside MSTSet. Remove any edges that now lead to vertices already in MSTSet.
PRIM(G, w, r)
// G = graph, w = weight function, r = root node
Q = G.N // Nodes not in MST
r.key = 0 // Start at root r
WHILE Q is not empty:
u = EXTRACT-MIN(Q)
FOR each n adjacent to u:
IF n is in Q AND w(u, n) < n.key:
n.parent = u
n.key = w(u, n)
Animation demonstrating Prim's algorithm finding the MST on a sample graph.
