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

全域木とは頂点を全て含む部分木のことです。そして、最小全域木とは「全域木のうち、辺の重みの総和が最小であるもの」です。

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

アルゴリズム

次の操作 1, 2 による貪欲法で、\(T\) が最小全域木になります。

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

\(T + e\) に閉路ができることと、\(e\) の両端点が \(T\) の同じ連結成分に含まれることが同値です。これは、Union Find によって \(\alpha(|V|)\) で判定できます（\(\alpha\) はアッカーマンの逆関数）。Union Find は

• union(x, y) : x と y が属する集合を合体する。
• equiv(x, y) : x と y が同じ集合に属するか判定する。

の二つのクエリを \(\alpha(|V|)\) で処理できるデータ構造です。従って、辺 \(\{x, y\}\) を採用した際に、union(x, y) とすることで、「\(x, y\) が同じ連結成分に属する」 \(\Leftrightarrow\) 「Union Find で \(x, y\) が同じ集合に属する」ということが成り立つのです。

辺を重みの昇順に並べなおすのは、\(O(|E|\log |E|)\) です。従って、全体では \(O(|E|\log |E|)\) がクラスカル法の計算量です。

アルゴリズムの正当性の証明（１）

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

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

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

アルゴリズムの正当性の証明（２）

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

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

注：(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;// 集合を表す木の親。parent[i] < 0 ならば i は根。
  
  UnionFind(int n) {
    parent.assign(n, -1);// 最初は 1 元集合の集まり。
  }
  // x が属する集合の代表元を返す
  int root(int x) {
    return parent[x] < 0 ? x : (parent[x] = root(parent[x]));// 経路圧縮
  }
  // x, y が属する集合を合体
  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;// y の親を x に
  }
  // x, y が同じ集合に属すか判定
  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;
  }
};
//　N は頂点数
// edges は辺のリスト
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(|E|+|V|\log |V|)\) ですから、クラスカル法の \(O(|E|\log |E|)\) より優れています。

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

おまけ

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

演習問題

解法：

• \(x \to -\infty\) の下でプリム法をしたとき、最小全域木に含まれる重み固定の辺は \(x\) に関わらず必ず最小全域木に含まれる。
• \(x \to \infty\) の下でプリム法をしたとき、最小全域木に含まれない重み固定の辺は \(x\) に関わらず必ず最小全域木に含まれない。
• それ以外の重み固定の辺 \(e\) は、プリム法をしたとき、 \(c(e) \leq x\) のとき、そのときに限り、最小全域木に含まれる。

以上より、重みに対する二分探索により求まる。

解答：この問題は、クラスカル法だと扱いづらく、プリム法かブルーフカ法か、或いはアドホックなアルゴリズムが適している。

ブルーフカ法：全頂点について重み 0 の辺と接続しているか調べるのは \(O(M)\) でできる。従って、ブルーフカ法は \(O(M \log(N))\) で動作する。

クラスカル法：\(G[U]\) の全域木が求まっているとする。次に採用するべき頂点は、\(U\) の隣接頂点のうち、重み 0 の辺が最も多く接続している頂点である。これは、重み 0 の辺を数えた時の次数でソートした頂点を Priority Queue で管理すればよい。全体で \(O(M \log(M))\) である。

その他 : 重み 1 の辺が高々 2m/n 個しか接続していない頂点 \(v\) が握手補題より取れる。\(v\) に接続する重み 0 の辺を全て採用すると頂点数が高々 \(\min(n, m/n) \leq \sqrt{m}\) の場合に帰着できる。あとは素直に最小全域木を求めれば良い。

解答 : \(c_1(T)/c_2(T) \geq t\) か？という判定問題は、\(c_1(T)/c_2(T) \geq t \Leftrightarrow \sum_{e \in E(T)} c_1(e)-tc_2(e) \geq0\) より、各辺 \(e\) が \(c_1(e)-tc_2(e)\) の重みの最小全域木の重みは 0 以上かという判定問題になる。従って t の二分探索により、解ける。

解答 : 最小全域木に不要な辺を削除しなければならない。
頂点 \(i, j, k\) が

• \(i > k, j > k\)
• \(A_i < A_k, A_j < A_k\)
• \(A_i + i < A_j + j\)

を満たすとする。\(i, j, k\) からなる3頂点の閉路で最も重い辺 \(\{j, k\}\) は選ばれることがないので削除してよい。
これを繰り返すと、各頂点 \(k\) に対して、\(i > k, A_i < A_k\) を満たす頂点で接続しうるものは \(A_i+i\) が最小の頂点だけである。\(i < k, A_i < A_k\) を満たす頂点についても同様。従って、辺の個数が \(O(N)\) に帰着できる。

A は昇順に並んでいると仮定して一般性を失わない。

• \(A_i < 0\) である頂点 \(i (\neq N)\) は頂点 \(N\) と結ぶ
• \(A_i = 0\) である頂点 \(i\) はどのように辺を張っても構わない
• \(A_i > 0\) である頂点 \(i(\neq 1)\) は頂点 \(1\) と結ぶ

解法