Thuật toán Kruskal là thuật toán tham lam hoạt động như sau:
1. Tạo một tập hợp tất cả các cạnh trong đồ thị.
2. Trong khi tập hợp trên không rỗng và chưa phủ hết đỉnh:
- Loại bỏ cạnh có trọng số nhỏ nhất từ tập hợp này
- Kiểm tra cạnh này có tạo chu trình hay chỉ nối 2 cây. Nếu tạo chu trình, loại bỏ cạnh này, ngược lại thêm vào cây của ta.
3. Khi xử lý xong, ta có một cây khung nhỏ nhất (minimum spanning tree).
Để triển khai thuật toán này, cần 2 cấu trúc dữ liệu thêm.
Thứ nhất, cần priority queue để giữ các cạnh theo thứ tự sắp xếp và lấy cạnh cần thiết mỗi lần lặp.
Thứ hai, cần cấu trúc dữ liệu disjoint set (tập hợp rời rạc). Cấu trúc dữ liệu disjoint-set (còn gọi union-find hoặc merge-find set) là cấu trúc theo dõi tập hợp các phần tử được phân hoạch thành nhiều tập hợp con rời rạc (không chồng chéo). Mỗi khi thêm nút mới vào cây, ta kiểm tra xem chúng đã kết nối chưa. Nếu có, thì có chu trình. Nếu không, ta union hai đỉnh của cạnh. Điều này thêm chúng vào cùng tập hợp con.
Hãy xem triển khai cấu trúc dữ liệu UnionFind hay DisjointSet:
Ví dụ
class UnionFind {
constructor(elements) {
// Số thành phần không liên thông
this.count = elements.length;
// Theo dõi các thành phần liên thông
this.parent = {};
// Khởi tạo cấu trúc dữ liệu sao cho tất cả phần tử có chính nó làm parent
elements.forEach(e => (this.parent[e] = e));
}
union(a, b) {
let rootA = this.find(a);
let rootB = this.find(b);
// Root cùng nhau nghĩa là đã liên thông.
if (rootA === rootB) return;
// Luôn làm phần tử có root nhỏ hơn làm parent.
if (rootA < rootB) {
if (this.parent[b] != b) this.union(this.parent[b], a);
this.parent[b] = this.parent[a];
} else {
if (this.parent[a] != a) this.union(this.parent[a], b);
this.parent[a] = this.parent[b];
}
}
// Trả về parent cuối cùng của nút
find(a) {
while (this.parent[a] !== a) {
a = this.parent[a];
}
return a;
}
// Kiểm tra liên thông của 2 nút
connected(a, b) {
return this.find(a) === this.find(b);
}
}
Bạn có thể kiểm tra bằng cách sau:
Ví dụ
let uf = new UnionFind(["A", "B", "C", "D", "E"]);
uf.union("A", "B");
uf.union("A", "C");
uf.union("C", "D");
console.log(uf.connected("B", "E"));
console.log(uf.connected("B", "D"));
Kết quả
Điều này sẽ cho ra kết quả:
false true
Bây giờ hãy xem triển khai thuật toán Kruskal dùng cấu trúc này:
Ví dụ
kruskalsMST() {
// Khởi tạo graph chứa MST
const MST = new Graph();
this.nodes.forEach(node => MST.addNode(node));
if (this.nodes.length === 0) {
return MST;
}
// Tạo Priority Queue
edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
// Thêm tất cả cạnh vào Queue:
for (let node in this.edges) {
this.edges[node].forEach(edge => {
edgeQueue.enqueue([node, edge.node], edge.weight);
});
}
let uf = new UnionFind(this.nodes);
// Lặp cho đến khi khám phá hết nút hoặc queue rỗng
while (!edgeQueue.isEmpty()) {
// Lấy dữ liệu cạnh dùng destructuring
let nextEdge = edgeQueue.dequeue();
let nodes = nextEdge.data;
let weight = nextEdge.priority;
if (!uf.connected(nodes[0], nodes[1])) {
MST.addEdge(nodes[0], nodes[1], weight);
uf.union(nodes[0], nodes[1]);
}
}
return MST;
}
Bạn có thể kiểm tra bằng cách sau:
Ví dụ
let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");
g.addEdge("A", "C", 100);
g.addEdge("A", "B", 3);
g.addEdge("A", "D", 4);
g.addEdge("C", "D", 3);
g.addEdge("D", "E", 8);
g.addEdge("E", "F", 10);
g.addEdge("B", "G", 9);
g.addEdge("E", "G", 50);
g.kruskalsMST().display();
Kết quả
Điều này sẽ cho ra kết quả:
A->B, D B->A, G C->D D->C, A, E E->D, F F->E G->B