Prim's Algorithm
Prim's Algorithm builds a Minimum Spanning Tree (MST) by starting with a single node and "growing" the tree outward. At every step, it finds the cheapest edge that connects a node inside the growing tree to a node outside of it. This greedy approach continues until all nodes are part of the tree, ensuring the total weight of all edges is as low as possible. It is perfect for problems like designing cost-effective road or utility networks.
Pseudocode
MST = empty set
mark src as visited
while MST does not span all vertices:
(u, v) = cheapest edge where
u ∈ visited and v ∉ visited
add edge (u, v) to MST
mark v as visited
Step by Step
- Initialize an empty set of edges for the MST.
- Start with an arbitrary vertex and mark it as visited (part of MST).
- Find the cheapest edge connecting a vertex in the MST to a vertex outside the MST.
- Add this edge to the MST and mark the new vertex as visited.
- Repeat until all vertices are part of the MST.
AI Summary
Curious to Learn More?
Hand-picked resources to deepen your understanding
© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0.