Thuật toán Kruskal là một thuật toán tham lam hoạt động như sau -
1. Nó tạo ra một tập hợp tất cả các cạnh trong biểu đồ.
2. Trong khi tập hợp trên không trống và không phải tất cả các đỉnh đều được bao phủ,
- Nó loại bỏ cạnh trọng lượng tối thiểu khỏi tập hợp này
- Nó kiểm tra xem cạnh này có đang hình thành một chu trình hay chỉ là kết nối 2 cây. Nếu nó tạo thành một chu kỳ, chúng tôi loại bỏ cạnh này, nếu không, chúng tôi thêm nó vào cây của chúng tôi.
3. Khi quá trình trên hoàn tất, chúng ta có một cây bao trùm tối thiểu.
Để triển khai thuật toán này, chúng ta cần thêm 2 cấu trúc dữ liệu.
Đầu tiên, chúng ta cần một hàng đợi ưu tiên mà chúng ta có thể sử dụng để giữ các cạnh theo thứ tự được sắp xếp và nhận được cạnh cần thiết của chúng ta trên mỗi lần lặp.
Tiếp theo, chúng ta cần một cấu trúc dữ liệu tập hợp rời rạc. Cấu trúc dữ liệu tập hợp rời rạc (còn được gọi là cấu trúc dữ liệu liên hợp-tìm hoặc hợp nhất tìm tập hợp) là cấu trúc dữ liệu theo dõi một tập hợp các phần tử được phân chia thành một số tập con rời rạc (không chồng chéo). Bất cứ khi nào chúng tôi thêm một nút mới vào một cây, chúng tôi sẽ kiểm tra xem chúng đã được kết nối chưa. Nếu có, thì chúng ta có một chu kỳ. Nếu không, chúng ta sẽ tạo một hợp nhất của cả hai đỉnh của cạnh. Thao tác này sẽ thêm chúng vào cùng một tập hợp con.
Hãy để chúng tôi xem xét việc triển khai cấu trúc dữ liệu UnionFind hoặc DisjointSet &minsu;
Ví dụ
class UnionFind {
constructor(elements) {
// Number of disconnected components
this.count = elements.length;
// Keep Track of connected components
this.parent = {};
// Initialize the data structure such that all
// elements have themselves as parents
elements.forEach(e => (this.parent[e] = e));
}
union(a, b) {
let rootA = this.find(a);
let rootB = this.find(b);
// Roots are same so these are already connected.
if (rootA === rootB) return;
// Always make the element with smaller root the 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];
}
}
// Returns final parent of a node
find(a) {
while (this.parent[a] !== a) {
a = this.parent[a];
}
return a;
}
// Checks connectivity of the 2 nodes
connected(a, b) {
return this.find(a) === this.find(b);
}
} Bạn có thể kiểm tra điều này bằng cách sử dụng -
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")); Đầu ra
Điều này sẽ cung cấp đầu ra -
false true
Bây giờ chúng ta hãy xem việc triển khai thuật toán của Kruskal bằng cách sử dụng cấu trúc dữ liệu này -
Ví dụ
kruskalsMST() {
// Initialize graph that'll contain the MST
const MST = new Graph();
this.nodes.forEach(node => MST.addNode(node));
if (this.nodes.length === 0) {
return MST;
}
// Create a Priority Queue
edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
// Add all edges to the 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);
// Loop until either we explore all nodes or queue is empty
while (!edgeQueue.isEmpty()) {
// Get the edge data using 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 điều này bằng cách sử dụng -
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(); Đầu ra
Điều này sẽ cung cấp đầu ra -
A->B, D B->A, G C->D D->C, A, E E->D, F F->E G->B