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