Java语言中的Kruskal算法
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