Javascriptでのプリムのアルゴリズム

Primのアルゴリズムは、重み付き無向グラフの最小スパニングツリーを見つける欲張りアルゴリズムです。すべての頂点を含むツリーを形成するエッジのサブセットを検出し、ツリー内のすべてのエッジの合計の重みが最小化されます。

アルゴリズムは、ツリーから別の頂点への可能な限り安価な接続を追加する各ステップで、任意の開始頂点から一度に1つの頂点でこのツリーを構築することによって動作します。

プリムのアルゴリズムはどのように機能しますか？

プリムのアルゴリズムがどのように機能するかを示す図を見てみましょう-

1.ルートノードとして任意のノードを選択します。この場合、PrimのスパニングツリーのルートノードとしてSノードを選択します。このノードは任意に選択されるため、任意のノードをルートノードにすることができます。なぜどのビデオもルートノードになり得るのか不思議に思うかもしれません。したがって、答えは、スパニングツリーにグラフのすべてのノードが含まれ、グラフが接続されているため、ツリーの残りの部分に結合するエッジが少なくとも1つ必要です。

2.出力エッジを確認し、コストの低いエッジを選択します。ルートノードSを選択すると、S、A、およびS、Cがそれぞれ重み7と8の2つのエッジであることがわかります。エッジS、Aは、他のエッジよりも小さいため、選択します。

ここで、ツリーS-7-Aは1つのノードとして扱われ、そこから出ているすべてのエッジをチェックします。コストが最も低いものを選択し、ツリーに含めます。

このステップの後、S-7-A-3-Cツリーが形成されます。ここで、それを再びノードとして扱い、すべてのエッジを再度チェックします。ただし、最小のコストエッジのみを選択します。この場合、C-3-Dは新しいエッジであり、他のエッジのコスト8、6、4などよりも低くなります。

ノードDを追加した後 スパニングツリーに対して、同じコストで2つのエッジ、つまりD-2-TとD-2-Bが出てきます。したがって、どちらかを追加できます。しかし、次のステップでは、最小のコストとしてエッジ2が再び生成されます。したがって、両方のエッジが含まれるスパニングツリーを表示しています。

次に、コードに同じものを実装する方法を見てみましょう-

例

primsMST() {
   // Initialize graph that'll contain the MST
   const MST = new Graph();
   if (this.nodes.length === 0) {
      return MST;
   }


   // Select first node as starting node
   let s = this.nodes[0];


   // Create a Priority Queue and explored set
   let edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
   let explored = new Set();
   explored.add(s);
   MST.addNode(s);


   // Add all edges from this starting node to the PQ taking weights as priority
   this.edges[s].forEach(edge => {
      edgeQueue.enqueue([s, edge.node], edge.weight);
   });


   // Take the smallest edge and add that to the new graph
   let currentMinEdge = edgeQueue.dequeue();
   while (!edgeQueue.isEmpty()) {


      // COntinue removing edges till we get an edge with an unexplored node
      while (!edgeQueue.isEmpty() && explored.has(currentMinEdge.data[1])) {
         currentMinEdge = edgeQueue.dequeue();
      }
      let nextNode = currentMinEdge.data[1];


      // Check again as queue might get empty without giving back unexplored element
      if (!explored.has(nextNode)) {
         MST.addNode(nextNode);
         MST.addEdge(currentMinEdge.data[0], nextNode, currentMinEdge.priority);
         // Again add all edges to the PQ
         this.edges[nextNode].forEach(edge => {
            edgeQueue.enqueue([nextNode, edge.node], edge.weight);
         });


         // Mark this node as explored 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
   *
*/

最もコストのかかるエッジを削除し、スパニングツリーを作成しました。