Prim's Algorithm

Prim's algorithm is a **greedy algorithm** that finds a Minimum Spanning Tree (MST) for a weighted, undirected graph. It begins growing the tree from an arbitrary root vertex, expanding the network link-by-link until every single node is bound together cleanly without any closed loops.

The Cut Property

At each step, the algorithm isolates the nodes currently inside the tree from those remaining outside. This dividing line is known as a Cut. Prim's algorithm looks at all edges crossing this cut (the frontier paths) and adds the absolute cheapest link to the tree.