Javascriptでのクラスカルのアルゴリズム

---

クラスカルのアルゴリズムは、次のように機能する欲張りアルゴリズムです-

1.グラフ内のすべてのエッジのセットを作成します。

2.上記のセットは空ではなく、すべての頂点がカバーされているわけではありませんが、

• このセットから最小ウェイトエッジを削除します
• このエッジがサイクルを形成しているか、2本の木を接続しているだけかをチェックします。サイクルを形成する場合は、このエッジを破棄します。それ以外の場合は、ツリーに追加します。

3.上記の処理が完了すると、最小スパニングツリーが作成されます。

このアルゴリズムを実装するには、さらに2つのデータ構造が必要です。

まず、エッジを並べ替えられた順序に保ち、各反復で必要なエッジを取得するために使用できる優先キューが必要です。

次に、素集合データ構造が必要です。素集合データ構造（union-findデータ構造またはmerge-find setとも呼ばれます）は、いくつかの互いに素な（重複しない）サブセットに分割された要素のセットを追跡するデータ構造です。ツリーに新しいノードを追加するたびに、それらがすでに接続されているかどうかを確認します。はいの場合、サイクルがあります。いいえの場合、エッジの両方の頂点を結合します。これにより、それらが同じサブセットに追加されます。

UnionFindまたはDisjointSetデータ構造の実装を見てみましょう＆minsu;

例

class UnionFind {
   constructor(elements) {
      // Number of disconnected components
      this.count = elements.length;

      // Keep Track of connected components
      this.parent = {};

      // Initialize the data structure such that all
      // elements have themselves as parents
      elements.forEach(e => (this.parent[e] = e));
   }

   union(a, b) {
      let rootA = this.find(a);
      let rootB = this.find(b);

      // Roots are same so these are already connected.
      if (rootA === rootB) return;

      // Always make the element with smaller root the parent.
      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];
      }
   }

   // Returns final parent of a node
   find(a) {
      while (this.parent[a] !== a) {
         a = this.parent[a];
      }
      return a;
   }

   // Checks connectivity of the 2 nodes
   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

次に、このデータ構造を使用したクラスカルのアルゴリズムの実装を見てみましょう-

例

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

   // Create a Priority Queue
   edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);

   // Add all edges to the Queue:
   for (let node in this.edges) {
      this.edges[node].forEach(edge => {
         edgeQueue.enqueue([node, edge.node], edge.weight);
      });
   }

   let uf = new UnionFind(this.nodes);

   // Loop until either we explore all nodes or queue is empty
   while (!edgeQueue.isEmpty()) {
      // Get the edge data using destructuring
      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