DSA Prim’s Algorithm
DSA – Prim’s Algorithm (Minimum Spanning Tree)
(Concept • Steps • Example • Dry Run • Code • Complexity • Interview Tips)
Prim’s Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, weighted, undirected graph.
Idea in one line:
Grow the MST one vertex at a time by always choosing the minimum weight edge that connects a new vertex.
1️⃣ What Problem Does Prim’s Algorithm Solve?
Given
-
A connected, undirected, weighted graph
Find
-
A Minimum Spanning Tree
-
Total weight is minimum
-
No cycles
-
Exactly V − 1 edges
2️⃣ When to Use Prim’s Algorithm
| Scenario | Use Prim’s? |
|---|---|
| Dense graph | ✅ Best choice |
| Sparse graph | ⚠️ Kruskal better |
| Negative weights | ✅ Allowed |
| Directed graph | ❌ Not applicable |
3️⃣ Core Greedy Idea
-
Start from any vertex
-
Repeatedly pick the minimum weight edge
-
The edge must:
-
Connect MST → non-MST vertex
-
Not form a cycle
-
Similar to Dijkstra, but goal is minimum total cost, not shortest path.
4️⃣ Step-by-Step Example
Start from A
| Step | Picked Edge | MST Nodes | Total Weight |
|---|---|---|---|
| 1 | A–B (2) | A,B | 2 |
| 2 | B–C (3) | A,B,C | 5 |
| 3 | C–D (5) | A,B,C,D | 10 |
MST complete (V−1 edges)
5️⃣ Algorithm Steps
-
Pick any start vertex
-
Mark it as visited
-
Push all connected edges into min-heap
-
Extract minimum edge
-
If it connects to an unvisited vertex:
-
Add to MST
-
Mark vertex visited
-
-
Repeat until all vertices included
6️⃣ Prim’s Algorithm – C++ (Priority Queue)
7️⃣ Time & Space Complexity
| Implementation | Time Complexity |
|---|---|
| Adjacency Matrix | O(V²) |
| Priority Queue (Adj List) | O(E log V) |
Space Complexity: O(V + E)
8️⃣ Prim vs Dijkstra (Very Important)
| Feature | Prim | Dijkstra |
|---|---|---|
| Goal | Minimum spanning tree | Shortest path |
| Cycles | ❌ Not allowed | Allowed |
| Negative edges | ✅ | ❌ |
| Output | V−1 edges | Distance array |
9️⃣ Common Mistakes
❌ Using Prim on disconnected graph
❌ Applying it to directed graph
❌ Forgetting to use min-heap
❌ Confusing it with Dijkstra
🔟 Interview Questions
Q1. Why Prim uses greedy approach?
👉 Choosing locally minimum edge leads to global minimum MST
Q2. Can Prim start from any vertex?
👉 Yes, MST weight remains same
Q3. Is MST always unique?
👉 Only when all edge weights are distinct
Final Summary
✔ Prim’s Algorithm finds Minimum Spanning Tree
✔ Greedy + Priority Queue
✔ Best for dense graphs
✔ Time complexity: O(E log V)
✔ Core topic for DSA & interviews
