Javascript 中的 Prim 算法
web developmentfront end technologyjavascript
Prim 算法是一种贪婪算法，用于为加权无向图找到最小生成树。它找到形成包含每个顶点的树的边的子集，其中树中所有边的总权重最小化。
该算法通过从任意起始顶点一次构建一个顶点来运行此树，每一步都从树到另一个顶点添加最便宜的连接。
Prim 算法如何工作?
让我们看一下 Prim 算法如何工作的说明 −
1. 选择任意节点作为根节点:在这种情况下，我们选择 S 节点作为 Prim 生成树的根节点。此节点是任意选择的，因此任何节点都可以是根节点。有人可能想知道为什么任何视频都可以成为根节点。所以答案是，在生成树中，图的所有节点都包括在内，并且由于它是连通的，因此必须至少有一条边将其连接到树的其余部分。
2. 检查传出边并选择成本较低的边:选择根节点 S 后，我们看到 S、A 和 S、C 是两条边，权重分别为 7 和 8。我们选择边 S、A，因为它小于另一条边。
现在，树 S-7-A 被视为一个节点，我们检查从它发出的所有边。我们选择成本最低的那个并将其包含在树中。
完成此步骤后，S-7-A-3-C 树就形成了。现在我们再次将其视为一个节点，并再次检查所有边。但是，我们只会选择成本最低的边。在这种情况下，C-3-D 是新边，它比其他边的成本低成本 8、6、4 等。
将节点 D 添加到生成树后，我们现在有两条具有相同成本的边从生成树中出来，即 D-2-T 和 D-2-B。因此，我们可以添加其中任何一个。但下一步将再次产生边 2 作为最低成本。因此，我们展示的是包含两条边的生成树。
现在让我们看看如何在代码中实现相同的功能 −
示例
primsMST() {
// 初始化包含 MST 的图
const MST = new Graph();
if (this.nodes.length === 0) {
return MST;
}
// 选择第一个节点作为起始节点
let s = this.nodes[0];
// 创建优先级队列和探索集
let edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
let explored = new Set();
explored.add(s);
MST.addNode(s);
// 以权重为优先级，将所有从此起始节点开始的边添加到 PQ
this.edges[s].forEach(edge => {
edgeQueue.enqueue([s, edge.node], edge.weight);
});
// 取最小边并将其添加到新图中
let currentMinEdge = edgeQueue.dequeue();
while (!edgeQueue.isEmpty()) {
// 继续移除边，直到我们得到一个具有未探索节点的边
while (!edgeQueue.isEmpty() && explored.has(currentMinEdge.data[1])) {
currentMinEdge = edgeQueue.dequeue();
}
let nextNode = currentMinEdge.data[1];
// 再次检查，因为队列可能会变空而不返回未探索的元素
if (!explored.has(nextNode)) {
MST.addNode(nextNode);
MST.addEdge(currentMinEdge.data[0], nextNode, currentMinEdge.priority);
// 再次将所有边添加到 PQ
this.edges[nextNode].forEach(edge => {
edgeQueue.enqueue([nextNode, edge.node], edge.weight);
});
// 将此节点标记为已探索 explored.add(nextNode);
s = nextNode;
}
}
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.primsMST().display();
输出
将给出输出 −
A->B, D B->A, G D->A, C, E C->D E->D, F G->B F->E
请注意，我们的初始图是 −
示例
/** * A * / | \ * C | B * \ | | * D G * | / * E * | * F */
输出
我们当前的图表看起来像 −
/** * A * |\ * C | B * \ | | * D G * | * E * | * F * */
我们已经删除了最昂贵的边，现在有一个生成树。
