最小全域木を \(O(\min(n^2,m\log(n)))\) で求めるアルゴリズム（\(m\):辺数、\(n\):頂点数）であるブルーフカ法を解説します。

最小全域木とは、各辺 \(e\) に対して重み \(c(e)\) が定まったグラフの全域木 \(T\) のうち、重み \(\sum_{e\in T} c(e)\) 最小のものです。

ブルーフカ法は、クラスカル法やプリム法と比較して、唯一ソートがいらないアルゴリズムです。他の二つの方法はソートがボトルネックになっています。

アルゴリズム

1. \(G\)が1頂点になるまで次の操作を繰り返します：
1. 各頂点 \(v\) について、接続する辺のうち重み最小の辺 \(e_v\) を見つけます。
2. 各 \(e_v\) を最小全域木の辺として（縮約を解いて）採用します。
3. 各 \(e_v\) を縮約して、\(G \leftarrow G/e_v\) とします。

(iii) で縮約する辺がサイクルをなすのは、サイクルの辺の重みが全て同じである場合だけです。もし頂点 \(0,1,\ldots,k-1\) がこの順（\(i,i\pm1 \bmod k\) が隣接）でサイクルを成しており、各頂点の重み最小の辺が \(f_0,f_1,\ldots,f_{k-1}\) だとします。すると、\(f_0 \geq f_1 \geq \cdots \geq f_{k-1} \geq f_0\) となり、全て等号で成立します。従って、どの辺を捨ててもよく、Union Find でサイクルの判定をすればよいです。Union by Rank/Size の Union Find の木のランクが \(O(E\log(E))\) であることから、経路圧縮をすれば計算量は \(O(E \log(E))\) で抑えられます。後述の平面グラフに線形時間で応用したい場合は、ラベルの辞書順で順序付けるなど、重みが異なる場合に帰着する必要があります。

(iii) も同様に Union Find で縮約すればよいです。後述の平面グラフに線形時間で応用したい場合は \(e_1, e_2, \ldots, e_{|G|}\) で形成される森の各連結成分を DFS で求めて縮約してから、辺を全て張りなおせば \(O(m)\) でできます。

(i)-(iii) を一巡するたびに頂点数が少なくとも半減します。(i) で辺数の \(O(m)\) がかかるので、全体では \(O(m \log(n))\) です。多重辺を除去しないので、(i) の \(O(m)\) はこれ以上改善できません。

以上の計算量解析は、グラフを隣接リストで保持した場合についてです。グラフを隣接行列で保持すると、多重辺を除去できます。(i)-(iii) の \(i\) 回目のループでは 頂点数 \(O(n/2^i)\)、辺数 \(O(n^2/2^i)\) なので、計算量は \(O(\sum n^2/2^i)=O(n^2)\) となります。グラフが密な場合、隣接行列の方が高速です。

グラフが密になるまで隣接リストのブルーフカ法を行った後、隣接行列に切り替えることで計算量を最適化できます。\(O(\log(n^2/m))\) 回、(i)-(iii)のループを繰り返すと、頂点数は \(O(n/2^{\log(n^2/m)}) = O(m/n)\) になります。ここから、隣接行列に切り替えると、\(O((m/n)^2)=O(m)\) 掛かり、全体では \(O(m\log(n^2/m))\) です。

あとの平面グラフの項で述べますが、基数ソートを利用すれば、\(O(m)\) 時間で多重辺の除去ができるので、隣接リストのみでこの計算量を達成できます。

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

各頂点について、接続する重み最小の辺を採用してよいことを証明します。

平面グラフ： \(O(n)\)

平面グラフの場合、\(O(n)\) でブルーフカ法は終了します[1]。

一つ目のカギは、平面グラフの辺を縮約しても平面グラフであることです。平面グラフは縮約について閉じています。このことから、入力が平面グラフならば、ブルーフカ法の途中のグラフも常に平面グラフです。

二つ目のカギは二通りあります。

平面グラフの辺数を利用

一つ目の方法では平面グラフの辺の個数が \(O(n)\) であることを利用します。

\(i\) 回目の (i)-(iii) のループでは頂点の個数が \(O(n/2^i)\) ですから、辺の個数も平面性より \(O(n/2^i)\) となります。\(i\) について和を取って、\(O(n)\) が全体の計算量になります。

縮約で、多重辺が生じうることに注意してください。計算量を改善するには、多重辺を消去する必要があります。なぜなら \(m \leq 3n-6\) は多重辺・自己辺のない平面グラフについてだからです。多重辺を見つけるには、辺 \((u,v)\) を \(u+nv\) として基数 \(n\) の基数ソートすればよいです。基数 \(n\) で2桁の数のソートなので \(O(n)\) 時間です。多重辺が生じた際は、重みの大きい方を捨てます。

平面グラフの次数を利用

二つ目の方法では次数 12 以下の頂点が \(n/2\) 個以上あることを用います。

ブルーフカ法の各ループ(i)-(iii)で次数 12 以下の頂点の辺のみを縮約することにします。すると、重み最小の辺はそれぞれ \(O(1)\) で見つかります。また、次数 12 以下の辺は \(n/2\) 個以上あるので、頂点数は \(3n/4\) 頂点以下になります。従って全体では \(O(\sum (3/4)^i n)=O(n)\) となります。

「次数12以下の頂点が \(n/2\) 個以上」は多重辺がない場合についてなので、多重辺を取り除く必要があることに注意してください。

プリム法と合体 : \(O(m\log\log(n))\)

フィボナッチヒープを用いたプリム法 \(O(m + n\log(n))\) と組み合わせて、\(O(m\log\log(n))\) にできます。\(O(\log\log(n))\) 回、ブルーフカ法の (i)-(iii) のループを行います。すると、頂点数が \(O(n/2^{\log\log(n)})=O(n/\log(n))\) 個になります。ここからプリム法に切り替えると、更に \(O(m+n)\) 掛かります。合計で \(O(m\log\log(n))\) です。\(m=o(n\log(n)/\log\log(n))\) のとき、プリム法・ブルーフカ法より高速です。

Yaoのアルゴリズム

\(v\) に接続する辺の集合 \(E(v)\) に対して、中央値の中央値を \(k\) 個に分割されるまで使うと、昇順に並べた時の \(i(E/k)\) から \((i+1)(E/k)\) 番目までの辺が集合 \(S_{v}^i\) として得られる。計算量は \(O(E\log(k))\)。ブルーフカ法でコスト最小の辺を探すとき、\(S_v^0, S_v^1, \ldots \) のうち、\(i\) が最小の非空な \(S_v^i\) だけみることにする。頂点の縮約が起きた時も、そのような \(S_v^i\) だけマージする。最小全域木に辺が採用されて、注目していた \(S_v^i\) が空になった時に初めて、\(S_v^{i+1}\) を扱う。このようにすると、最小の辺を探す計算量は各フェーズごとに \(O(E/k)\) になる。よって、\(k = \log(E)\) とすると、全体で \(O(E \log\log V)\) になる。

Fredman のアルゴリズム

縮約後の各頂点の次数が \(d = \Omega(2^{ E / V})\) となるまで、各頂点からプリム法を行います。フィボナッチヒープを使うと、ヒープのサイズは \(O(d)\) で抑えられるため、計算量は \(O(V \log (d) + E) = O(E)\) になります。縮約後の頂点数は \(O(2E / d)\) になります。以下、これを繰り返します。\(i\) 回目のフェーズにおける頂点の次数を \(d_i\) とすると、\(d_{i+1} = \Omega(2^{d_i/2})\) なので、\(O(E \log^*(V))\) で最小全域木が求まります。

おまけ

STARTを押すと、ブルーフカ法を可視化します。余計分かりにくいな(^^;)

問題演習

各区間 [L, R] に対して、交差する区間 [L’, R’] であって、

• R < R’ であって共通部分最小
• L’ < L であって共通部分最小

であるものを列挙する。これだけで、連結グラフになるので、ブルーフカ法のアルゴリズムの理屈より、最小全域木が元のグラフと一致する。最小全域木の構築自体はクラスカル法を使うのが楽だと思う。

前問とほとんど同じ。

参考文献

1. Mareš, Martin. Two linear time algorithms for MST on minor closed graph classes. ETH Zurich, 2002.
   • バケットソートで多重辺の除去が deterministic に線形でできるとあったのですが、分かりませんでした。更新：Misawaさんに教えてもらい理解できました。
2. Problem Set no. 1 — Minimum spanning trees
   隣接行列と隣接リストを切り替えると計算量削減できるということが書いてあります
3. Yao, Andrew Chi-Chih. “An O (| E| log log| V|) algorithm for finding minimum spanning trees.” Information Processing Letters 4 (1975): 21-23.
4. Fredman, Michael L., and Robert Endre Tarjan. “Fibonacci heaps and their uses in improved network optimization algorithms.” Journal of the ACM (JACM) 34.3 (1987): 596-615.
5. Cheriton, David, and Robert Endre Tarjan. “Finding minimum spanning trees.” SIAM journal on computing 5.4 (1976): 724-742.
6. Gabow, Harold N., et al. “Efficient algorithms for finding minimum spanning trees in undirected and directed graphs.” Combinatorica 6.2 (1986): 109-122.