数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究JavaScript 中的克鲁斯卡尔算法
克鲁斯卡尔算法是一种贪心算法，其工作原理如下：
1. 它创建图中所有边的集合。
2. 当上述集合不为空且未覆盖所有顶点时，
- 它从该集合中移除权重最小的边
- 它检查此边是否形成循环或只是连接两棵树。如果它形成循环，则我们丢弃此边，否则我们将其添加到我们的树中。
3. 当上述处理完成后，我们就得到了最小生成树。
为了实现此算法，我们需要另外两种数据结构。
首先，我们需要一个优先级队列，我们可以使用它来按排序顺序保存边，并在每次迭代时获取所需的边。
接下来，我们需要一个不相交集数据结构。不相交集数据结构（也称为联合查找数据结构或合并查找集）是一种数据结构，它跟踪一组元素，这些元素被划分为多个不相交（不重叠）的子集。每当我们将一个新节点添加到树中时，我们将检查它们是否已连接。如果是，则我们有一个循环。如果不是，我们将对边的两个顶点进行联合。这将使它们添加到同一个子集中。
让我们看看 UnionFind 或 DisjointSet 数据结构的实现；
示例
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);
}
}您可以使用以下方法进行测试：
示例
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
现在让我们看看使用此数据结构实现克鲁斯卡尔算法：
示例
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;
}您可以使用以下方法进行测试：
示例
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
更新于: 2020-06-15
1K+ 次查看
广告