Skip to content →

最小全域木:クラスカル法

クラスカル法(Kruskal’s algorithm)とは、最小全域木を求めるアルゴリズムです。

全域木とは頂点を全て含む部分木のことです。そして、最小全域木とは「全域木のうち、辺の重みの総和が最小であるもの」です。クラスカル法が扱う問題を正確に述べると、次のようになります:

各辺 \(e \in E\) に対して重み \(c(e)\) が定まった連結グラフ \(G=(V,E)\) があります。 全域木 \(T=(V,F)\) のうち、\(\sum_{e \in F} c(e)\) が最小になるものを求めてください

クラスカル法は、最小全域木を \(O(M\log M)\) で求められます(\(M\):辺数)。最小全域木を求めるアルゴリズムとして他に、プリム法ブルーフカ法があります。

アルゴリズム

次の操作 1, 2 によって、\(T\) が最小全域木になります。

  1. \(T\) を空グラフとします。
  2. 辺を重みの昇順に全て取り出します。取り出した辺 \(e\) を加えたグラフ \(T + e\) に閉路ができないならば、\(T \leftarrow T + e\) とし、さもなくば \(e\) を捨てます。

\(T + e\) に閉路ができることと、\(e\) の両端点が \(T\) の同じ連結成分に含まれることが同値です。これは、Union Findによって \(\alpha(|V|)\) で判定できます(\(\alpha\)はアッカーマンの逆関数)。辺を重みの昇順に並べなおすのは、\(O(M\log M)\) です。従って、全体では \(O(M\log M)\) がクラスカル法の計算量です。

アルゴリズムの正当性の証明(1)

二つの方法で正当性を証明してみます。こちらは直接的な方法です。

証明:\(e \in E\) を重み最小の辺とします。\(e\) を含む最小全域木が存在することを示します。\(e\) を持つ最小全域木がないと仮定します。任意の最小全域木 \(T\) の 基本閉路 \(C_e\) の \(e\) 以外の辺 \(f\) の重みは \(c(e)\) と等しいです。さもなくば、\(T-f+e\) の重みは \(T\) より小さく最小性に矛盾。\(c(e)=c(f)\) なので、\(T-f+e\) も最小全域木になり、\(e\) を辺に持つ最小全域木が存在しないことに矛盾。

以上より、\(e\) を最小全域木の辺として採用してもよいことが分かりました。\(e\) を縮約した \(G/e\) の最小全域木は、縮約を解くと \(G\) の最小全域木です。\(G/e\) に対して上記の論法を繰り返すと、クラスカルのアルゴリズムが得られます。

\(e\) として、特定の連結成分 \(A\) に接続する辺のうち重み最小のものを選んでもよいことが上記の証明から分かります。基本閉路 \(C_e\) には \(e\) 以外の \(A\) に接続する辺 \(f\) が存在するからです。\(A\) を固定すると、プリム法になります。\(A\) を全ての連結成分に対して順に適用すると、ブルーフカ法になります。また、クラスカル法とプリム法の中間のような \(k\) 点から最小全域木を大きくしていくといった戦略も可能であることが分かります。

平面グラフの時は次数 \(5\) 以下の頂点が存在することと、マイナークローズドであることから、その頂点を \(A\) として選ぶと \(O(n\alpha(n))\) でできることが分かります。

アルゴリズムの正当性の証明(2)

アルゴリズムの正当性の証明でカギになるのは次の定理です:

全域木 \(T\) について、次の二つは同値である。

  1. \(T\) は最小全域木である。
  2. 任意の \(e \in E \setminus E(T)\) について、\(T\) に関する基本閉路 \(C_e\) の各辺の重みは \(c(e)\) 以下である。

クラスカル法では \(c(e)\) の昇順に辺を追加するので、アルゴリズムの途中で常に条件 (2) が成立します。条件 (2) が成立するので、生成される全域木は最小全域木になります。この定理を証明できれば、クラスカル法の正当性が得られることが分かりました。

証明:
(1) \(\Rightarrow\) (2) を示します。対偶を取ります。\(e \in E \setminus E(T),e’ \in C_e, c(e) > c(e’)\) となる辺 \(e, e’\) が存在したとします。すると、\(T-e+e’\) は全域木であり、更にその重みは \(T\) に比べて、\(c(e)-c(e’)\) だけ減少します。これは、\(T\) が最小でないことを意味します。

(2) \(\Rightarrow\) (1) を示します。対偶を取ります。任意の最小でない全域木 \(T\) が、(2) の反例となる辺を持つことを示せばよいです。最小全域木 \(T’\) を一つ固定します。\(T\) の葉 \(u\) と \(u\) に接続する辺 \(e\) を一ペア取ります。\(T’\) において、\(T’-v\) の \(u\) を含む連結成分と \(v\) を繋ぐ辺 \(f\) がただ一つ存在します。

① \(c(f) > c(e)\) の場合:\(T’-f+e\) の方が \(T’\) よりコストの小さい全域木ですので、\(T’\) が最小全域木であることに矛盾。

② \(c(f) < c(e)\) の場合: \(f\) が (2) の反例となる辺です。

③ \(c(f)=c(e)\) の場合:\(T’ \leftarrow T’-f+e\) としても、\(T’\) は最小全域木なので一般性を失いません。\(e\) を縮約した\(T/e\), \(T’/e\) はともに全域木です。特に \(T’/e\) は最小全域木であり、\(T/e\) は最小全域木ではありません。従って、\(|V|\) に関する帰納法により \(T/e\) と \(T’/f\) で (2) の反例となる辺が取れます(base case は1頂点のグラフで (2) \(\Rightarrow\) (1) は成立)。

注:(2) \(\Rightarrow\) (1) を示すのに、\(e\) を葉に接続する辺として取りました。しかし、より一般に、任意の \(e \in T\) について、\(T-e+f\) が全域木となる、ある辺 \(f \in T’\) が存在することが言えます。

実装

C++ での実装を示します:

#include <vector>
#include <algorithm>
using namespace std;

struct UnionFind {
  vector<int> parent;
  
  UnionFind(int n) {
    parent.assign(n, -1);
  }
  
  int root(int x) {
    return parent[x] < 0 ? x : (parent[x] = root(parent[x]));
  }
  
  void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) return;
    if (parent[x] > parent[y]) swap(x, y);
    parent[x] += parent[y];
    parent[y] = x;
  }
  
  bool equiv(int x, int y) {
    return root(x) == root(y);
  }
};

struct Edge {
  int u, v;
  long long cost;
  bool operator < (Edge const& o) {
    return cost < o.cost;
  }
};

vector<edge> minimum_spanning_tree(int N, vector<edge> edges) {
  vector<edge> tree_edges; 
  UnionFind uf(N);
  sort(edges.begin(), edges.end());
  
  for (Edge &e : edges) {
    if (uf.equiv(e.u, e.v)) continue;
    uf.unite(e.u, e.v);
    tree_edges.push_back(e);
  }
  return tree_edges;
}

プリム法との比較

最小全域木を求めるアルゴリズムとして、ほかにプリム法が知られています。プリム法の計算量は \(O(M+N\log N)\) ですから、クラスカル法の \(O(M\log M)\) より優れています(\(N\):頂点数、\(M\):辺数)。

ですが、特殊な場合にはクラスカル法の方がプリム法より計算量が小さくなります。例えば、ソートが線形時間でできる場合(バケットソートや基数ソート)です。\(O(\alpha(N)M)\) になります。 他にも、頂点の部分集合に対して、何度も最小全域木を求める場合です。各部分集合の全域木を求める度にソートをする必要はなく、最初に一度だけすればよいです。

おまけ

STARTを押すとクラスカル法が始まります。


Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA