JavaScriptで実装するプリム法：最小全域木を求めるアルゴリズムの基本と実装例

プリム法（Prim's Algorithm）とは

プリム法は、重み付き無向グラフから最小全域木（MST: Minimum Spanning Tree）を求めるための貪欲法（グリーディアルゴリズム）です。グラフ内のすべての頂点を含み、かつ辺の重みの合計が最小になるような辺の部分集合（木）を見つけ出します。

アルゴリズムは、任意の開始頂点から木の構築を始め、1ステップごとに「木に属する頂点」と「木に属さない頂点」をつなぐ辺の中から、最もコスト（重み）の小さいものを1本追加していくことで動作します。

プリム法の動作の流れ

以下の図を使って、プリム法がどのように動作するのかを順番に見ていきましょう。

ステップ1：任意のノードをルートとして選ぶ

まず、任意のノードを全域木のルートノードとして選択します。ここでは例として、ノードSをルートノードに選びました。ルートはどのノードでも構いません。なぜなら、全域木にはグラフのすべてのノードが含まれ、グラフが連結である以上、必ず少なくとも1本の辺で残りの木とつながるからです。

ステップ2：出ていく辺を確認し、コストが最小のものを選ぶ

ルートノードSを選んだ後、Sから出る辺を確認すると、重み7の「S-A」と重み8の「S-C」の2本があります。ここでは、よりコストの小さい「S-A」を選択します。

次に、S-7-Aという木をひとまとまりのノードとして扱い、そこから出ていくすべての辺を調べます。そして、その中で最もコストの低い辺を選んで木に追加します。

このステップの後、S-7-A-3-Cという木が形成されました。再びこれを1つのノードとして扱い、すべての辺を確認します。ただし選ぶのは最小コストの辺だけです。この例では、他の辺のコスト（8、6、4など）より小さい「C-3-D」が新しい辺として選ばれます。

ノードDを全域木に追加した後、Dからは同じコスト2の2本の辺（D-2-TとD-2-B）が出ています。この場合、どちらを先に追加しても問題ありません。いずれにしても次のステップでコスト2の辺が最小となるため、ここでは両方の辺を含む全域木を示しています。

JavaScriptでの実装

それでは、このアルゴリズムを実際にコードで実装する方法を見ていきましょう。

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

  // 開始ノードから出るすべての辺を、重みを優先度としてキューに追加
  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);

      // 新しいノードから出るすべての辺をキューに追加
      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
*/

MST適用後のグラフ

処理後のグラフは次のようになります。

/**
 *          A
 *          |\
 *       C  |  B
 *        \ |  |
 *          D  G
 *          |
 *          E
 *          |
 *          F
 *
*/

このように、最もコストの高い辺（重み100のA-C間など）を取り除くことで、全体の重みが最小となる全域木が完成しました。

計算量について

プリム法の計算量は、使用するデータ構造によって変わります。上記の実装のように優先度キュー（二分ヒープ）を使用した場合、計算量は O(E log V)（Eは辺の数、Vは頂点の数）となります。一方、隣接行列を使った単純な実装では O(V²) となり、辺の密度が高いグラフ（密なグラフ）ではこちらが有利になることもあります。

また、同じく最小全域木を求めるアルゴリズムとしてクラスカル法（Kruskal's algorithm）があります。プリム法は頂点を基準に木を成長させるのに対し、クラスカル法は辺を重みの昇順にソートして追加していく点が異なります。用途やグラフの性質に応じて使い分けるとよいでしょう。