Javascript 中的 Kruskal 算法
web developmentfront end technologyjavascript
Kruskal 算法是一种贪婪算法，其工作原理如下 −
1. 它创建图中所有边的集合。
2. 当上述集合不为空且并非所有顶点都被覆盖时，
- 它从该集合中删除最小权重边
- 它检查此边是形成循环还是仅连接 2 棵树。如果它形成循环，我们丢弃此边，否则我们将其添加到我们的树中。
3.完成上述处理后，我们就得到了一个最小生成树。
为了实现这个算法，我们还需要 2 个数据结构。
首先，我们需要一个优先级队列，我们可以使用它来保持边的排序顺序，并在每次迭代中获取所需的边。
接下来，我们需要一个不相交集数据结构。不相交集数据结构(也称为联合查找数据结构或合并查找集)是一种数据结构，它跟踪一组被划分为多个不相交(不重叠)子集的元素。每当我们向树中添加新节点时，我们都会检查它们是否已经连接。如果是，那么我们就有一个循环。如果不是，我们将边的两个顶点合并。这会将它们添加到同一个子集。
让我们看一下 UnionFind 或 DisjointSet 数据结构 &minsu; 的实现
示例
class UnionFind {
constructor(elements) {
// 断开连接的组件数
this.count = elements.length;
// 跟踪连接的组件
this.parent = {};
// 初始化数据结构，使所有
// 元素都以自己为父元素
elements.forEach(e => (this.parent[e] = e));
}
union(a, b) {
let rootA = this.find(a);
let rootB = this.find(b);
// 根相同，因此它们已经连接。
if (rootA === rootB) return;
// 始终将根较小的元素作为父元素。
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];
}
}
// 返回节点的最终父节点
find(a) {
while (this.parent[a] !== a) {
a = this.parent[a];
}
return a;
}
// 检查 2 个节点的连接性
connected(a, b) {
return this.find(a) === this.find(b);
} }
您可以使用以下方法进行测试 −
示例
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"));
输出
这将给出输出 −
false true
现在让我们看看使用此数据结构 − 实现 Kruskal 算法
示例
kruskalsMST() {
// 初始化包含 MST 的图
const MST = new Graph();
this.nodes.forEach(node => MST.addNode(node));
if (this.nodes.length === 0) {
return MST;
}
// 创建优先级队列
edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
// 将所有边添加到队列:
for (let node in this.edges) {
this.edges[node].forEach(edge => {
edgeQueue.enqueue([node, edge.node], edge.weight);
});
}
let uf = new UnionFind(this.nodes);
// 循环直到我们探索所有节点或队列为空
while (!edgeQueue.isEmpty()) {
// 使用解构获取边缘数据
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;
}
您可以使用以下方法进行测试 −
示例
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();
输出
这将给出输出 −
A->B, D B->A, G C->D D->C, A, E E->D, F F->E G->B
