Chapter 37: DSA Prim’s Algorithm

DSA Prim’s Algorithm – Let’s understand this topic properly and in depth, like I’m sitting next to you with a whiteboard, drawing the graph step by step, explaining every single decision slowly and clearly, showing exactly what happens in each step, and most importantly helping you understand when and why Prim’s algorithm is used, how it differs from Kruskal, and why interviewers love asking it.

What is Prim’s Algorithm?

Prim’s algorithm is one of the two classic algorithms (the other being Kruskal) that finds the Minimum Spanning Tree (MST) of a connected, undirected, weighted graph.

Minimum Spanning Tree means:

• A tree that connects all vertices
• Has no cycles
• Has the minimum possible total edge weight among all such trees

Prim’s algorithm builds the MST by growing a single tree, starting from any vertex, and repeatedly adding the smallest possible edge that connects a vertex already in the tree to a vertex outside the tree.

Core Idea (very simple intuition)

Imagine you are building a network of roads between cities and you want to connect all cities with the cheapest possible total road length without creating loops.

Prim’s way of thinking:

1. Start with any one city — it is now part of our network.
2. Look at all possible roads going out from the cities already in the network to cities outside the network.
3. Always choose the cheapest such road and build it — add that new city to the network.
4. Repeat until all cities are connected.

This is exactly what Prim’s does — it grows the MST one vertex at a time.

Important Properties of Prim’s Algorithm

• Works on connected, undirected, weighted graphs
• Edge weights must be non-negative (most implementations)
• Produces correct MST
• Can start from any vertex — result will be valid MST (possibly different if multiple MSTs exist)
• Uses priority queue (min-heap) to always pick the cheapest next edge

Classic Example Graph (we’ll solve step-by-step)

Vertices: A, B, C, D, E, F

Edges with weights:

• A-B: 4
• A-C: 2
• B-C: 1
• B-D: 5
• C-D: 8
• C-E: 10
• D-E: 2
• D-F: 6
• E-F: 3

Visual (imagine this on whiteboard):

Goal: Find MST starting from vertex A

Step-by-step execution of Prim’s Algorithm

Initialize:

• MST set = empty
• Visited set = empty
• Key (distance to add this vertex) = {A:0, others: ∞}
• Priority queue = [(0, A)]
• Previous (to reconstruct tree) = all None

Step 1 Extract min = A (key = 0) Add A to MST Mark A visited

Relax neighbors of A:

• B: 0 + 4 = 4 < ∞ → key[B] = 4, prev[B] = A
• C: 0 + 2 = 2 < ∞ → key[C] = 2, prev[C] = A

Queue now: (2, C), (4, B)

Step 2 Extract min = C (key = 2) Add C to MST Mark C visited

Relax neighbors of C:

• A: already visited → skip
• D: 2 + 8 = 10 < ∞ → key[D] = 10, prev[D] = C
• E: 2 + 10 = 12 < ∞ → key[E] = 12, prev[E] = C

Queue now: (4, B), (10, D), (12, E)

Step 3 Extract min = B (key = 4) Add B to MST Mark B visited

Relax neighbors of B:

• A: visited → skip
• C: visited → skip
• D: 4 + 5 = 9 < 10 → update key[D] = 9, prev[D] = B

Queue now: (9, D), (12, E), (10, D) ← old entry still there (we ignore outdated when we extract)

Step 4 Extract min = D (key = 9) Add D to MST Mark D visited

Relax neighbors of D:

• B: visited → skip
• C: visited → skip
• E: 9 + 2 = 11 < 12 → update key[E] = 11, prev[E] = D
• F: 9 + 6 = 15 < ∞ → key[F] = 15, prev[F] = D

Queue now: (11, E), (12, E), (15, F)

Step 5 Extract min = E (key = 11) Add E to MST Mark E visited

Relax neighbors of E:

• C: visited → skip
• D: visited → skip
• F: 11 + 3 = 14 < 15 → update key[F] = 14, prev[F] = E

Queue now: (14, F), (15, F)

Step 6 Extract min = F (key = 14) Add F to MST Mark F visited

No new neighbors → done

Final MST edges (from previous array):

• A → C (2)
• A → B (4)
• B → D (5)
• D → E (2)
• E → F (3)

Total weight = 2 + 4 + 5 + 2 + 3 = 16

Prim’s Algorithm Code (standard interview version)

Prim’s vs Kruskal – Very Important Interview Comparison

Rule of thumb (very common interview answer):

“I will choose Prim’s when the graph is dense (E ≈ V²) or when we want to grow from a specific starting vertex. I will choose Kruskal when the graph is sparse (E << V²) or when Union-Find is already familiar and edge sorting is acceptable.”

Summary – Prim’s Algorithm in one line each

• Finds Minimum Spanning Tree by growing a single tree
• Uses greedy strategy + priority queue to always add cheapest edge to tree
• Time complexity: O((V + E) log V) with binary heap
• Works on connected, undirected, weighted graphs with non-negative weights
• One of the two classic MST algorithms (along with Kruskal)
• Very frequently asked in medium/hard graph problems
• Real-world use: network design, clustering, circuit design, etc.

Would you like to go deeper into Prim’s or related topics?

Very natural next steps:

• Prim’s algorithm full step-by-step dry run with priority queue changes
• Prim vs Kruskal – detailed comparison on same graph
• How Prim’s is similar to Dijkstra (very common interview question)
• Prim’s for dense graphs vs Kruskal for sparse
• Implement Prim’s with adjacency matrix (sometimes asked)
• Applications of MST (real problems + interview questions)

Just tell me which direction you want to go next — I’ll explain it in the same detailed, step-by-step, human-teacher style with clear examples and visuals! 😊