50. Minimum Spanning Trees (MST): Prim's Algorithm Concept

A Spanning Tree of a graph is a subgraph that connects all the vertices together, without any cycles. A Minimum Spanning Tree (MST) is a spanning tree where the sum of the weights of the edges is minimized.

Prim's Algorithm (Greedy Approach)

Prim's algorithm builds the MST iteratively by adding edges that connect a new vertex to the growing tree set. It is a local optimization strategy.

1. Start with an arbitrary source vertex S in the MST.
2. Repeat V-1 times:
   • Select the edge (U, V) that connects a vertex U already in the MST to an unvisited vertex V such that the weight of the edge (U, V) is minimal.
   • Add this minimum-weight edge and vertex V to the MST.

Prim's is implemented efficiently using a Min Heap (Priority Queue), much like Dijkstra's, to quickly select the next smallest edge.