---

Minimum Spanning Tree (MST) — Detailed Explanation

A Minimum Spanning Tree (MST) is a subset of edges of a connected, undirected, weighted graph such that:

1. It connects all vertices (spanning)
2. It has no cycles (tree)
3. Total weight of edges is minimum possible

---

1. Basic Concepts

Spanning Tree

A spanning tree of a graph G(V, E) is:

• Acyclic (no cycles)
• Has V – 1 edges
• Connects all vertices

A graph can have many spanning trees.

---

Minimum Spanning Tree

Among all possible spanning trees, the one with least total weight is called the Minimum Spanning Tree (MST).

---

2. Applications of MST

MST is extremely important in real-world network design:

• Network layouts (LAN, WAN, fiber networks)
• Roads and railway networks
• Electrical grids
• Telecommunication routing
• Image segmentation
• Cluster analysis (machine learning)
• Approximation algorithms (Traveling Salesman Problem)

---

3. Important Properties of MST

A. Unique MST Condition

If all edge weights are distinct, the MST is unique.

B. MST has exactly V – 1 edges

For a graph with n vertices, MST must have:

[
n – 1 \text{ edges}
]

C. Cycle Property

For any cycle, the heaviest edge cannot be in the MST.

D. Cut Property

For any cut, the minimum weight edge crossing the cut must be in MST.

(Used heavily in algorithms)

---

4. Algorithms to Find MST

There are two classic MST algorithms:

1. Kruskal’s Algorithm (Greedy)
2. Prim’s Algorithm (Greedy)

---

5. Kruskal’s Algorithm

Approach:

Greedy → Choose the shortest edges first without forming cycles.

Steps:

1. Sort all edges by increasing weight.
2. Initialize MST as empty.
3. Pick edges in sorted order:
   • Add edge to MST if it does NOT form a cycle.
4. Use Disjoint Set Union (DSU) to detect cycles quickly.
5. Stop when MST has V – 1 edges.

Time Complexity:

• Sorting edges → O(E log E)
• Union-Find operations → ≈ O(α(n)) ≈ constant

So final complexity:

[
O(E \log E) \approx O(E \log V)
]

Best for:

• Sparse graphs (E is small)
• Graph given as edge list
• Algorithm used in Kruskal’s MST + DSU questions

---

6. Prim’s Algorithm

Approach:

Grow MST starting from one vertex → always pick the minimum weight edge connecting MST to outside vertex.

Steps:

1. Start from any vertex.
2. Put all edges from this vertex into a priority queue.
3. Select the minimum weight edge that connects to a new vertex.
4. Add the vertex to MST.
5. Repeat until all vertices are included.

Time Complexity:

Using Min-Heap (Priority Queue):

[
O(E \log V)
]

Using Fibonacci Heap:

[
O(E + V \log V)
]

Best for:

• Dense graphs
• Graph given as adjacency list
• Networking problems

---

7. Kruskal vs Prim — Comparison Table

Feature	Kruskal	Prim
Working	Edge-based	Vertex-based
Data Structure	DSU (Union-Find)	Min-Heap / Priority Queue
Graph Type	Sparse	Dense
Starting Point	No start needed	Requires start vertex
Complexity	O(E log V)	O(E log V)
MST	Independent trees merged	Grows one tree

---

8. Example

Weighted graph edges:

Edge	Weight
A–B	1
A–C	3
B–C	2
C–D	4
B–D	5

MST using Kruskal:

Pick edges in sorted order:

1. A–B (1)
2. B–C (2)
3. A–C (3) → cycle, skip
4. C–D (4)

MST edges:

• A–B
• B–C
• C–D

Total weight = 1 + 2 + 4 = 7

---

9. Why MST Works — Proof of Correctness (Short)

Both Prim and Kruskal use the Cut Property:

The minimum weight edge crossing any cut must be part of the MST.

This ensures greedy choice is always optimal.

---

10. MST does NOT work for:

✘ Directed graphs
✘ Graphs with negative cycles (but can have negative weights)
✘ Graphs that are disconnected (MST exists only for connected graphs)

---

Summary

A Minimum Spanning Tree (MST) is:

• A spanning tree with minimum total weight
• connect all vertices
• has V–1 edges
• no cycles

Algorithms:

• Kruskal: sort edges, use DSU
• Prim: grow tree using min-edge
• Both run in O(E log V) time

Used heavily in:

• Networks
• Routing
• Clustering
• Optimization problems

---