Cây bao phủ (Spanning Tree) là một khái niệm quan trọng trong lý thuyết đồ thị. Một cây bao phủ của một đồ thị vô hướng là một cây con bao gồm tất cả các đỉnh của đồ thị và một số cạnh sao cho tất cả các đỉnh đều liên thông và không có chu trình. Nếu đồ thị có
𝑉
V đỉnh, thì cây bao phủ sẽ có
𝑉
−
1
V−1 cạnh.
Có nhiều cách để tìm cây bao phủ của một đồ thị, nhưng phổ biến nhất là các thuật toán để tìm cây bao phủ nhỏ nhất (Minimum Spanning Tree - MST). Hai thuật toán nổi tiếng nhất cho việc này là Thuật toán Prim và Thuật toán Kruskal.
Thuật toán Prim
Thuật toán Prim bắt đầu từ một đỉnh và mở rộng cây bao phủ bằng cách thêm vào các cạnh có trọng số nhỏ nhất kết nối đỉnh hiện tại với các đỉnh chưa được thăm.
Mô tả giải thuật:
Khởi tạo: Bắt đầu từ một đỉnh bất kỳ. Đánh dấu đỉnh này là một phần của cây bao phủ.
Chọn cạnh nhỏ nhất: Chọn cạnh có trọng số nhỏ nhất kết nối một đỉnh trong cây bao phủ với một đỉnh ngoài cây bao phủ.
Thêm cạnh vào cây: Thêm đỉnh mới vào cây bao phủ.
Lặp lại: Lặp lại quá trình cho đến khi tất cả các đỉnh đều được thêm vào cây bao phủ.
Pseudocode:
python
Sao chép mã
import sys
def primMST(graph):
V = len(graph)
key = [sys.maxsize] * V # Trọng số nhỏ nhất để kết nối đến đỉnh i
parent = [None] * V # Lưu đỉnh cha của i trong cây MST
key[0] = 0 # Đặt trọng số của đỉnh đầu tiên là 0
mstSet = [False] * V # Theo dõi các đỉnh đã được bao gồm trong MST
parent[0] = -1 # Đỉnh đầu tiên không có cha
for _ in range(V):
min_key = sys.maxsize
u = -1
for v in range(V):
if not mstSet[v] and key[v] < min_key:
min_key = key[v]
u = v
mstSet[u] = True
for v in range(V):
if graph[u][v] > 0 and not mstSet[v] and key[v] > graph[u][v]:
key[v] = graph[u][v]
parent[v] = u
return parent
# Ví dụ sử dụng:
graph = [
[0, 2, 0, 6, 0],
[2, 0, 3, 8, 5],
[0, 3, 0, 0, 7],
[6, 8, 0, 0, 9],
[0, 5, 7, 9, 0]
]
parent = primMST(graph)
print("Edge \tWeight")
for i in range(1, len(graph)):
print(f"{parent[i]} - {i} \t{graph[i][parent[i]]}")
Thuật toán Kruskal
Thuật toán Kruskal xây dựng cây bao phủ nhỏ nhất bằng cách sắp xếp tất cả các cạnh theo trọng số và thêm chúng vào cây bao phủ theo thứ tự từ nhỏ đến lớn, miễn là không tạo thành chu trình.
Mô tả giải thuật:
Khởi tạo: Sắp xếp tất cả các cạnh theo trọng số.
Chọn cạnh nhỏ nhất: Lấy cạnh có trọng số nhỏ nhất và kiểm tra xem nó có tạo chu trình với các cạnh đã chọn không.
Thêm cạnh vào cây: Nếu không tạo chu trình, thêm cạnh vào cây bao phủ.
Lặp lại: Lặp lại quá trình cho đến khi cây bao phủ có
𝑉
−
1
V−1 cạnh.
Pseudocode:
python
Sao chép mã
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def addEdge(self, u, v, w):
self.graph.append([u, v, w])
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1
def KruskalMST(self):
result = []
i = 0
e = 0
self.graph = sorted(self.graph, key=lambda item: item[2])
parent = []
rank = []
for node in range(self.V):
parent.append(node)
rank.append(0)
while e < self.V - 1:
u, v, w = self.graph[i]
i += 1
x = self.find(parent, u)
y = self.find(parent, v)
if x != y:
e += 1
result.append([u, v, w])
self.union(parent, rank, x, y)
print("Constructed MST:")
for u, v, weight in result:
print(f"{u} -- {v} == {weight}")
# Ví dụ sử dụng:
g = Graph(4)
g.addEdge(0, 1, 10)
g.addEdge(0, 2, 6)
g.addEdge(0, 3, 5)
g.addEdge(1, 3, 15)
g.addEdge(2, 3, 4)
g.KruskalMST()
Kết luận
Cả hai thuật toán Prim và Kruskal đều hiệu quả trong việc tìm cây bao phủ nhỏ nhất của một đồ thị, nhưng chúng có cách tiếp cận khác nhau và mỗi cái có ưu điểm riêng. Thuật toán Prim thường được sử dụng cho các đồ thị dày đặc (dense graph) trong khi thuật toán Kruskal hiệu quả hơn với các đồ thị thưa (sparse graph).
code c++cây bao phủ
ChatGPT
Dưới đây là triển khai các giải thuật tìm cây bao phủ nhỏ nhất (Minimum Spanning Tree) bằng C++ cho cả thuật toán Prim và Kruskal.
Thuật toán Prim
cpp
Sao chép mã
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int minKey(vector<int>& key, vector<bool>& mstSet, int V) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
void printMST(vector<int>& parent, vector<vector<int>>& graph, int V) {
cout << "Edge \tWeight\n";
for (int i = 1; i < V; i++)
cout << parent[i] << " - " << i << " \t" << graph[i][parent[i]] << " \n";
}
void primMST(vector<vector<int>>& graph, int V) {
vector<int> parent(V); // Array to store constructed MST
vector<int> key(V); // Key values used to pick minimum weight edge in cut
vector<bool> mstSet(V); // To represent set of vertices not yet included in MST
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;
key[0] = 0; // First vertex is always root of MST
parent[0] = -1; // First node is always root of MST
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet, V);
mstSet[u] = true;
for (int v = 0; v < V; v++)
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
printMST(parent, graph, V);
}
int main() {
int V = 5;
vector<vector<int>> graph = {
{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0}
};
primMST(graph, V);
return 0;
}
Thuật toán Kruskal
cpp
Sao chép mã
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Edge {
public:
int src, dest, weight;
};
class Graph {
public:
int V, E;
vector<Edge> edges;
Graph(int V, int E) {
this->V = V;
this->E = E;
}
void addEdge(int u, int v, int w) {
Edge edge = {u, v, w};
edges.push_back(edge);
}
int find(vector<int>& parent, int i) {
if (parent[i] == i)
return i;
return find(parent, parent[i]);
}
void Union(vector<int>& parent, vector<int>& rank, int x, int y) {
int xroot = find(parent, x);
int yroot = find(parent, y);
if (rank[xroot] < rank[yroot])
parent[xroot] = yroot;
else if (rank[xroot] > rank[yroot])
parent[yroot] = xroot;
else {
parent[yroot] = xroot;
rank[xroot]++;
}
}
void KruskalMST() {
vector<Edge> result; // Tạo mảng kết quả MST
// Sắp xếp các cạnh theo trọng số
sort(edges.begin(), edges.end(), [](Edge a, Edge b) {
return a.weight < b.weight;
});
vector<int> parent(V);
vector<int> rank(V, 0);
for (int i = 0; i < V; i++)
parent[i] = i;
int e = 0; // Số cạnh đã chọn vào MST
int i = 0; // Chỉ số cạnh hiện tại
while (e < V - 1 && i < E) {
Edge next_edge = edges[i++];
int x = find(parent, next_edge.src);
int y = find(parent, next_edge.dest);
if (x != y) {
result.push_back(next_edge);
Union(parent, rank, x, y);
e++;
}
}
cout << "Constructed MST:\n";
for (auto& edge : result)
cout << edge.src << " -- " << edge.dest << " == " << edge.weight << endl;
}
};
int main() {
int V = 4;
int E = 5;
Graph g(V, E);
g.addEdge(0, 1, 10);
g.addEdge(0, 2, 6);
g.addEdge(0, 3, 5);
g.addEdge(1, 3, 15);
g.addEdge(2, 3, 4);
g.KruskalMST();
return 0;
}