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.
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.
Curious to Learn More?
Hand-picked resources to deepen your understanding
As an Udemy Associate, I earn from qualifying purchases. This helps support the site at no extra cost to you.
© 2025 SEE Algorithms. Code licensed under MIT, content under CC BY-NC 4.0.