Chapter 36: DSA Minimum Spanning Tree
DSA Minimum Spanning Tree (MST) – Let’s understand this topic properly and in depth, like I’m sitting next to you with a whiteboard, drawing graphs step by step, explaining every single detail slowly and clearly, comparing the two main algorithms side by side, showing multiple examples with numbers, and most importantly telling you why MST is one of the most important and most frequently asked graph topics in interviews and real-world applications.
What is a Minimum Spanning Tree?
A Minimum Spanning Tree (MST) of a connected, undirected, weighted graph is a tree (subset of edges) that:
- Connects all vertices (spans the whole graph)
- Contains no cycles
- Has the minimum possible total edge weight among all such spanning trees
In simple words:
MST is the cheapest way to connect all points without forming any loops.
Real-life examples where MST is used
| Real-world situation | Vertices | Edges & weights | Why MST is useful |
|---|---|---|---|
| Electrical wiring / cable network | Houses / buildings | Distance or cable cost | Minimize total cable length/cost |
| Computer network design | Routers / switches | Connection cost / distance | Cheapest way to connect all devices |
| Approximate solutions to Traveling Salesman Problem | Cities | Road distances | MST + some heuristics |
| Cluster analysis in data science | Data points | Distance between points | Build hierarchical clustering |
| Image segmentation | Pixels | Similarity / distance | Group similar regions |
| Road / railway network planning | Cities / junctions | Construction cost | Cheapest connected infrastructure |
Important Properties of MST
| Property | Meaning / Consequence |
|---|---|
| Number of edges in MST | V − 1 (where V = number of vertices) |
| MST of a graph is always a tree | Connected + no cycles |
| A graph can have multiple MSTs | If there are several combinations with same total weight |
| MST exists only if graph is connected | If disconnected → Minimum Spanning Forest |
| Adding any edge not in MST creates a cycle | And that edge would be the heaviest in that cycle (Cut Property) |
Two Most Important Algorithms for MST
There are two classic algorithms — both are very frequently asked in interviews:
- Kruskal’s Algorithm
- Prim’s Algorithm
Both give correct MST, but they work differently and are suitable for different graph types.
1. Kruskal’s Algorithm
Key idea: Sort all edges by increasing weight → keep adding the smallest edge that does not form a cycle.
Uses Union-Find (Disjoint Set Union – DSU) to detect cycles efficiently.
Steps:
- Sort all edges in non-decreasing order of weight
- Initialize Union-Find — each vertex is its own component
- For each edge in sorted order:
- If the two vertices are not in same component (no cycle)
- Add the edge to MST
- Union the two components
- If the two vertices are not in same component (no cycle)
- Stop when MST has V−1 edges
Example Graph (same as before)
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
Sorted edges (weight ascending):
- B-C : 1
- A-C : 2
- D-E : 2
- E-F : 3
- A-B : 4
- B-D : 5
- D-F : 6
- C-D : 8
- C-E : 10
Step-by-step:
- Add B-C (1) → components: {B,C}, others single
- Add A-C (2) → connects A to {B,C}
- Add D-E (2) → {D,E}
- Add E-F (3) → {D,E,F}
- Add A-B (4) → already connected → skip (cycle)
- Add B-D (5) → connects {A,B,C} with {D,E,F} → now all connected
- Stop! We have 5 edges (6 vertices − 1)
MST edges: B-C(1), A-C(2), D-E(2), E-F(3), B-D(5) Total weight = 1+2+2+3+5 = 13
Kruskal’s Code (most common interview style)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
class UnionFind: def __init__(self, size): self.parent = list(range(size)) self.rank = [0] * size def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): px, py = self.find(x), self.find(y) if px == py: return False if self.rank[px] < self.rank[py]: self.parent[px] = py elif self.rank[px] > self.rank[py]: self.parent[py] = px else: self.parent[py] = px self.rank[px] += 1 return True def kruskal(graph, V): # graph = list of [u, v, weight] edges = [] for u in graph: for v, w in graph[u]: if u < v: # avoid duplicate edges in undirected edges.append((w, u, v)) edges.sort() uf = UnionFind(V) mst = [] total_weight = 0 for w, u, v in edges: if uf.union(u, v): mst.append((u, v, w)) total_weight += w if len(mst) == V - 1: break return mst, total_weight |
2. Prim’s Algorithm
Key idea: Start from any vertex → repeatedly add the smallest edge that connects a visited vertex to an unvisited vertex.
Uses priority queue (min-heap) to always pick the closest unvisited vertex.
Steps:
- Start from any vertex → mark visited, add to MST
- While there are unvisited vertices:
- Find the minimum weight edge connecting a visited vertex to an unvisited vertex
- Add that edge to MST
- Mark the new vertex visited
- Stop when all vertices are visited
Prim’s is similar to Dijkstra — in fact, Prim’s is a special case of Dijkstra where we treat the MST as a “distance” from the current tree.
Prim’s vs Kruskal – Quick Comparison (very common interview question)
| Question / Property | Prim’s Algorithm | Kruskal’s Algorithm |
|---|---|---|
| Approach | Grows a single tree | Builds forest, combines components |
| Data structure | Priority queue (min-heap) | Union-Find |
| Time complexity (with binary heap) | O((V + E) log V) | O(E log E) ≈ O(E log V) |
| Time complexity (with Fibonacci heap) | O(E + V log V) | Not applicable |
| Best for | Dense graphs | Sparse graphs |
| Edge sorting required | No | Yes |
| Implementation complexity | Slightly more complex | Easier (Union-Find is simple) |
Rule of thumb (2025–2026 interview style):
“I will use Kruskal when the graph is sparse (few edges) or when Union-Find is already implemented. I will use Prim’s when the graph is dense or when I want to grow the tree from a single starting point.”
Summary – Minimum Spanning Tree in one line each
- MST connects all vertices with minimum total edge weight and no cycles
- Number of edges in MST = V − 1
- Two main algorithms: Kruskal (edge-based, Union-Find) and Prim (vertex-based, priority queue)
- Both run in near O(E log V) time with good implementation
- Kruskal → good for sparse graphs, Prim → good for dense graphs
- One of the top 5 most important graph algorithms in interviews
- Very common real-world use: network design, clustering, approximation algorithms
Would you like to go deeper into MST or related topics?
Very natural next steps:
- Kruskal step-by-step dry run with Union-Find
- Prim’s algorithm detailed execution with priority queue
- Kruskal vs Prim – which one to choose when
- How to find MST in disconnected graph (Minimum Spanning Forest)
- Applications of MST (real problems + interview questions)
- Bottleneck shortest path using MST
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! 😊
