Giao diện
MST — Minimum Spanning Tree Advanced
MST tìm tập cạnh với tổng trọng số nhỏ nhất để kết nối tất cả các đỉnh.
Tại sao MST?
MST xuất hiện trong rất nhiều bài toán thực tế:
┌─────────────────────────────────────────────────────────────────┐
│ MST APPLICATIONS │
├─────────────────────────────────────────────────────────────────┤
│ │
│ 🌐 NETWORK DESIGN 🔌 ELECTRICAL GRIDS │
│ ───────────────── ───────────────── │
│ Minimize cable cost Minimize wire length │
│ Connect all servers Power all houses │
│ │
│ 🚀 CLUSTER ANALYSIS 🗺️ ROAD PLANNING │
│ ───────────────── ────────────── │
│ Group similar items Connect cities cheaply │
│ Hierarchical clustering Minimize construction cost │
│ │
└─────────────────────────────────────────────────────────────────┘Định nghĩa
Spanning Tree: Cây con của graph, chứa tất cả đỉnh và V-1 cạnh (V = số đỉnh).
Minimum Spanning Tree: Spanning Tree với tổng trọng số nhỏ nhất.
Original Graph MST (total = 9)
────────────── ───────────────
2 2
A ───── B A ───── B
│\ │ │
3 │ \ 4 │ 5 3 │
│ \ │ │
C ───── D C ───── D
1 1
Edges: (A-B,2), (A-C,3), MST edges: (C-D,1), (A-B,2),
(A-D,4), (B-D,5), (A-C,3)
(C-D,1) Total weight: 1+2+3 = 6Algorithm 1: Prim's Algorithm
Ý tưởng
Greedy approach: Bắt đầu từ 1 đỉnh, liên tục thêm cạnh có trọng số nhỏ nhất nối đến đỉnh chưa thăm.
┌─────────────────────────────────────────────────────────────────┐
│ PRIM'S ALGORITHM │
├─────────────────────────────────────────────────────────────────┤
│ │
│ 1. Chọn đỉnh nguồn s │
│ 2. Thêm s vào MST │
│ 3. Repeat V-1 times: │
│ └─ Chọn cạnh (u,v) có weight nhỏ nhất │
│ với u ∈ MST, v ∉ MST │
│ └─ Thêm v vào MST │
│ │
└─────────────────────────────────────────────────────────────────┘Implementation với Priority Queue
cpp
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef pair<int, int> pii; // (weight, vertex)
class Graph {
private:
int V;
vector<vector<pii>> adj; // adj[u] = [(weight, v), ...]
public:
Graph(int vertices) : V(vertices), adj(vertices) {}
void addEdge(int u, int v, int weight) {
adj[u].emplace_back(weight, v);
adj[v].emplace_back(weight, u); // Undirected
}
// Prim's MST Algorithm
int primMST() {
// Min-heap: (weight, vertex)
priority_queue<pii, vector<pii>, greater<pii>> pq;
vector<int> key(V, INT_MAX); // Minimum edge weight to reach vertex
vector<bool> inMST(V, false); // Is vertex in MST?
vector<int> parent(V, -1); // Parent in MST (for reconstruction)
int mstWeight = 0;
// Start from vertex 0
key[0] = 0;
pq.emplace(0, 0); // (weight=0, vertex=0)
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
// Skip if already in MST
if (inMST[u]) continue;
// Add to MST
inMST[u] = true;
mstWeight += key[u];
// Explore neighbors
for (auto& [weight, v] : adj[u]) {
// If v not in MST and weight is smaller than current key
if (!inMST[v] && weight < key[v]) {
key[v] = weight;
parent[v] = u;
pq.emplace(weight, v);
}
}
}
// Print MST edges
cout << "MST Edges:" << endl;
for (int v = 1; v < V; ++v) {
if (parent[v] != -1) {
cout << " " << parent[v] << " -- " << v
<< " (weight: " << key[v] << ")" << endl;
}
}
return mstWeight;
}
};
int main() {
Graph g(5);
// 0
// /|\
// 2 | 3
// / | \
// 1---4---2
// \ | /
// 6 1 7
// \|/
// 3
g.addEdge(0, 1, 2);
g.addEdge(0, 3, 3);
g.addEdge(1, 2, 4);
g.addEdge(1, 3, 6);
g.addEdge(2, 3, 7);
g.addEdge(2, 4, 5);
g.addEdge(3, 4, 1);
int totalWeight = g.primMST();
cout << "\nTotal MST Weight: " << totalWeight << endl;
return 0;
}Output:
MST Edges:
0 -- 1 (weight: 2)
0 -- 3 (weight: 3)
1 -- 2 (weight: 4)
3 -- 4 (weight: 1)
Total MST Weight: 10Algorithm 2: Kruskal's Algorithm
Ý tưởng
Edge-centric approach: Sắp xếp tất cả cạnh theo trọng số tăng dần, thêm cạnh nếu không tạo cycle.
┌─────────────────────────────────────────────────────────────────┐
│ KRUSKAL'S ALGORITHM │
├─────────────────────────────────────────────────────────────────┤
│ │
│ 1. Sort tất cả cạnh theo weight (ascending) │
│ 2. Khởi tạo Union-Find với V components │
│ 3. For each edge (u, v, weight): │
│ └─ If u và v thuộc khác component: │
│ ├─ Thêm edge vào MST │
│ └─ Union(u, v) │
│ 4. Dừng khi MST có V-1 edges │
│ │
└─────────────────────────────────────────────────────────────────┘Union-Find (Disjoint Set Union)
cpp
class UnionFind {
private:
vector<int> parent, rank_;
public:
UnionFind(int n) : parent(n), rank_(n, 0) {
for (int i = 0; i < n; ++i) {
parent[i] = i; // Mỗi node là root của chính nó
}
}
// Path compression
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // Flatten tree
}
return parent[x];
}
// Union by rank
bool unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return false; // Already same component
// Attach smaller tree under larger tree
if (rank_[rootX] < rank_[rootY]) {
parent[rootX] = rootY;
} else if (rank_[rootX] > rank_[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank_[rootX]++;
}
return true;
}
};Complete Kruskal Implementation
cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
int u, v, weight;
bool operator<(const Edge& other) const {
return weight < other.weight;
}
};
class UnionFind {
private:
vector<int> parent, rank_;
public:
UnionFind(int n) : parent(n), rank_(n, 0) {
for (int i = 0; i < n; ++i) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
bool unite(int x, int y) {
int rootX = find(x), rootY = find(y);
if (rootX == rootY) return false;
if (rank_[rootX] < rank_[rootY]) swap(rootX, rootY);
parent[rootY] = rootX;
if (rank_[rootX] == rank_[rootY]) rank_[rootX]++;
return true;
}
};
int kruskalMST(int V, vector<Edge>& edges) {
// Sort edges by weight
sort(edges.begin(), edges.end());
UnionFind uf(V);
vector<Edge> mstEdges;
int mstWeight = 0;
for (const Edge& e : edges) {
// If adding this edge doesn't create cycle
if (uf.unite(e.u, e.v)) {
mstEdges.push_back(e);
mstWeight += e.weight;
// MST complete when we have V-1 edges
if (mstEdges.size() == V - 1) break;
}
}
// Print MST
cout << "MST Edges (Kruskal):" << endl;
for (const Edge& e : mstEdges) {
cout << " " << e.u << " -- " << e.v
<< " (weight: " << e.weight << ")" << endl;
}
return mstWeight;
}
int main() {
int V = 5;
vector<Edge> edges = {
{0, 1, 2},
{0, 3, 3},
{1, 2, 4},
{1, 3, 6},
{2, 3, 7},
{2, 4, 5},
{3, 4, 1}
};
int totalWeight = kruskalMST(V, edges);
cout << "\nTotal MST Weight: " << totalWeight << endl;
return 0;
}So sánh Prim vs Kruskal
| Aspect | Prim | Kruskal |
|---|---|---|
| Approach | Vertex-centric (grow tree) | Edge-centric (add edges) |
| Data Structure | Priority Queue + Adjacency List | Sorted Edges + Union-Find |
| Time Complexity | O(E log V) với binary heap | O(E log E) = O(E log V) |
| Space | O(V + E) | O(V + E) |
| Better for | Dense graphs | Sparse graphs |
| Edge list required? | No (adj list) | Yes |
Complexity Analysis
Prim's Algorithm
| Operation | Complexity |
|---|---|
| Initialize | O(V) |
| Extract-min (V times) | O(V log V) |
| Decrease-key (E times) | O(E log V) |
| Total | O((V + E) log V) = O(E log V) |
Kruskal's Algorithm
| Operation | Complexity |
|---|---|
| Sort edges | O(E log E) |
| Find (E times) | O(E α(V)) ≈ O(E) |
| Union (V-1 times) | O(V α(V)) ≈ O(V) |
| Total | O(E log E) = O(E log V) |
💡 α(V) — Inverse Ackermann
α(V) là inverse Ackermann function, gần như hằng số (≤ 4 với mọi V thực tế).
⚠️ Common Pitfalls
CẢNH BÁO
1. Duplicate edges trong Prim:
cpp
// ❌ SAI: Skip duplicate entries
if (inMST[u]) continue; // ✅ Phải check này!2. Quên undirected edges:
cpp
// ❌ SAI: Chỉ add 1 chiều
g.addEdge(0, 1, 5);
// ✅ ĐÚNG: Add cả 2 chiều
adj[u].push_back({weight, v});
adj[v].push_back({weight, u});3. Union-Find không path compression:
cpp
// ❌ SAI: No path compression → O(N) per find
int find(int x) {
while (parent[x] != x) x = parent[x];
return x;
}
// ✅ ĐÚNG: Path compression → O(α(N)) amortized
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}🎯 Practice Problems
| Problem | Difficulty | Focus |
|---|---|---|
| Minimum Spanning Tree (HackerRank) | Medium | Prim basic |
| Cities and Roads (CSES) | Medium | MST + counting |
| Minimum Cost to Connect All Points (LeetCode) | Medium | Kruskal/Prim |
| Optimize Water Distribution (LeetCode) | Hard | MST variant |