Javascript中的Prim算法

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);
         });


         //将此节点标记为exploredexplored.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
   *
*/

我们删除了最昂贵的边缘，现在有了生成树。