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