Prim's algorithm is a greedy method that finds the minimum spanning tree (MST) in a weighted undirected graph, connecting all vertices with the smallest possible total edge weight while avoiding cycles.
The algorithm starts with an arbitrary vertex and grows the MST one edge at a time. At each step, it selects the cheapest edge that connects a vertex already in the growing tree to another vertex not yet included.
For example, consider a graph with vertices A, B, C, D, and edges with weights: AB(1), AC(3), AD(5), BC(2), BD(4), CD(6). Starting with vertex A, the algorithm would first add edge AB (weight 1), then BC (weight 2), and finally CD (weight 6), resulting in an MST with total weight 9.
Prim's algorithm operates on weighted graphs, which can be represented using adjacency matrices or adjacency lists. The algorithm itself has two primary variants:
Prim's algorithm is widely used in network design, such as cable TV networks, water supply networks, and electrical grids, where the goal is to connect all nodes with minimal total connection cost. It's also applied in cluster analysis and approximation algorithms for the traveling salesman problem.
One common misconception is that Prim's algorithm always produces a unique MST. However, multiple MSTs may exist for the same graph, depending on tie-breaking rules during edge selection.
| Step | Action | Edge Added | Total Weight |
|---|---|---|---|
| 1 | Start with vertex A | - | 0 |
| 2 | Add cheapest edge from A | AB (1) | 1 |
| 3 | Add cheapest edge from A or B to unvisited vertices | BC (2) | 3 |
| 4 | Add cheapest edge from A, B, or C to unvisited vertices | CD (6) | 9 |
While both algorithms find MSTs, they differ in approach. Prim's algorithm grows the MST from a single vertex, while Kruskal's algorithm starts with the smallest edge and adds edges until all vertices are connected. Prim's is generally more efficient for dense graphs.