Prim’s Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected weighted graph. It starts with a single node and repeatedly adds the smallest edge that connects a visited node to an unvisited node, until all vertices are included.
Steps of Prim’s Algorithm:
1. Start with any node (usually vertex 0).
2. Mark the starting node as visited.
3. Among all edges from visited to unvisited nodes, pick the edge with the minimum weight.
4. Add the selected edge and its vertex to the MST.
5. Repeat steps 3–4 until all vertices are included in the MST.
Example:
Consider the following graph:
2
A ------- B
| \ |
3| \1 |4
| \ |
C ------- D
5
Vertices: A, B, C, D
Edges with weights:
AB = 2
AC = 3
AD = 1
BD = 4
CD = 5
Step-by-step using Prim’s Algorithm (Starting from A):
| Step | Visited Nodes | Chosen Edge | MST Edges | Total Cost |
|---|---|---|---|---|
1 |
A |
AD (1) |
AD |
1 |
2 |
A, D |
AB (2) |
AD, AB |
3 |
3 |
A, D, B |
AC (3) |
AD, AB, AC |
6 |
Now all vertices are visited, so the MST is complete.
Final MST Edges: AD, AB, AC
Total Minimum Cost = 6