隣接リスト表現によるプリム法の最小全域木（MST）アルゴリズム

このアルゴリズムは、前回紹介した隣接行列版のプリム法と基本的な流れは同じですが、唯一異なる点は、グラフ G(V, E) を隣接リストで表現しているところです。

隣接リスト表現を用いた場合の時間計算量は O(E log V) です。辺の数 E が頂点数 V に比べて少ない「疎なグラフ」では、隣接行列を使う O(V²) の実装よりも効率的に動作します。

プリム法とは、重み付き無向グラフから最小全域木（Minimum Spanning Tree：MST）を求める代表的な貪欲法アルゴリズムの一つです。本実装では、すでに木に組み込まれた頂点の集合を B、グラフの全頂点の集合を N として管理し、B と N − B をつなぐ辺の中から最もコストの小さいものを順に選びながら、木を成長させていきます。

入力と出力

入力：
コスト行列：

出力：
Edge: A--B And Cost: 1
Edge: B--E And Cost: 2
Edge: A--C And Cost: 3
Edge: A--D And Cost: 4
Edge: E--F And Cost: 2
Edge: F--G And Cost: 3
Total Cost: 15

アルゴリズム

prims(g: Graph, start)

入力 − グラフ g と、探索の起点となるシード頂点「start」

出力 − 辺を追加して構成された木（最小全域木）

Begin
    2つの集合 B と N を作成する
    開始ノードを集合 B に追加する

    グラフ g 内のすべての頂点 u について
        頂点 u を集合 N に追加する
    繰り返し終了

    B ≠ N である間、以下を繰り返す
        min := ∞
        グラフ g 内のすべての頂点 u について
            u が集合 B に含まれる場合
                u に隣接するすべての頂点 v について
                    v が (N − B) に含まれる場合
                        min ＞ 辺 uv のコスト である場合
                            min := 辺 uv のコスト
                            parent := u
                            node := v
                    繰り返し終了
            繰り返し終了
        繰り返し終了

        node を集合 B に挿入する
        parent から node への辺を木に追加する
    繰り返し終了

    木を返す
End

アルゴリズムのポイント

• 集合 B は「すでに最小全域木に組み込まれた頂点」、集合 N は「グラフの全頂点」を表します。
• 各ステップでは、B に属する頂点から N − B（未訪問の頂点）へ伸びる辺のうち、コストが最小のものを 1 本選択します。
• 選ばれた辺の相手側の頂点を B に移動させ、対応する辺を木に追加します。これをすべての頂点が B に含まれるまで繰り返します。

サンプルプログラム（C++）

#include<iostream>
#include<list>
#include<set>
using namespace std;

typedef struct nodes {
   int dest;
   int cost;
}node;

class Graph {
   int n;
   list<node> *adjList;
   private:
      void showList(int src, list<node> lt) {
         list<node> :: iterator i;
         node tempNode;

         for(i = lt.begin(); i != lt.end(); i++) {
            tempNode = *i;
            cout << "(" << src << ")---("<<tempNode.dest <<"|"<<tempNode.cost<<") ";
         }
         cout << endl;
      }

   public:
      Graph() {
         n = 0;
      }

      Graph(int nodeCount) {
         n = nodeCount;
         adjList = new list<node>[n];
      }

      void addEdge(int source, int dest, int cost) {
         node newNode;
         newNode.dest = dest;
         newNode.cost = cost;
         adjList[source].push_back(newNode);
      }

      void displayEdges() {
         for(int i = 0; i<n; i++) {
            list<node> tempList = adjList[i];
            showList(i, tempList);
         }
      }

      friend Graph primsMST(Graph g, int start);
};

set<int> difference(set<int> first, set<int> second) {
   set<int> :: iterator it;
   set<int> res;

   for(it = first.begin(); it != first.end(); it++) {
      if(second.find(*it) == second.end())
         res.insert(*it);    //2番目の集合に存在しない要素のみを追加
   }

   return res;    //集合(first − second)を返す
}

Graph primsMST(Graph g, int start) {
   int n = g.n;
   set<int> B, N, diff;
   Graph tree(n);       //グラフと同じノード数で木を作成
   B.insert(start);     //開始ノードを集合Bに挿入

   for(int u = 0; u<n; u++) {
      N.insert(u); //すべての頂点を集合Nに追加
   }

   while(B != N) {
      int min = 9999;          //無限大として扱う
      int v, par;
      diff = difference(N, B); //集合 N − B を求める

      for(int u = 0; u < n; u++) {
         if(B.find(u) != B.end()) {
            list<node>::iterator it;
            for(it = g.adjList[u].begin(); it != g.adjList[u].end(); it++) {
               if(diff.find(it->dest) != diff.end()) {
                  if(min > it->cost) {
                     min = it->cost;    //コストを更新
                     par = u;
                     v = it->dest;
                  }
               }
            }
         }
      }

      B.insert(v);
      tree.addEdge(par, v, min);
      tree.addEdge(v, par, min);
   }
   return tree;
}

main() {
   Graph g(7), tree(7);
   g.addEdge(0, 1, 1);
   g.addEdge(0, 2, 3);
   g.addEdge(0, 3, 4);
   g.addEdge(0, 5, 5);
   g.addEdge(1, 0, 1);
   g.addEdge(1, 3, 7);
   g.addEdge(1, 4, 2);
   g.addEdge(2, 0, 3);
   g.addEdge(2, 4, 8);
   g.addEdge(3, 0, 4);
   g.addEdge(3, 1, 7);
   g.addEdge(4, 1, 2);
   g.addEdge(4, 2, 8);
   g.addEdge(4, 5, 2);
   g.addEdge(4, 6, 4);
   g.addEdge(5, 0, 5);
   g.addEdge(5, 4, 2);
   g.addEdge(5, 6, 3);
   g.addEdge(6, 4, 4);
   g.addEdge(6, 5, 3);

   tree = primsMST(g, 0);
   tree.displayEdges();
}

コードの解説

Graph クラスは、隣接リスト（list<node> の配列）によってグラフを保持し、addEdge メソッドで始点・終点・コストを持つ辺を登録します。primsMST 関数では、補助関数 difference によって未訪問頂点の集合 N − B を求め、B に属する各頂点の隣接リストを走査して最小コストの辺を探索します。見つかった頂点を B に追加し、その辺を双方向で結果の木に加えることで、最終的に最小全域木が完成します。

出力結果

Edge: A--B And Cost: 1
Edge: B--E And Cost: 2
Edge: A--C And Cost: 3
Edge: A--D And Cost: 4
Edge: E--F And Cost: 2
Edge: F--G And Cost: 3
Total Cost: 15