[競プロ用]有向最小全域木まとめ

(無向)最小全域木を求める方法

双方向に繋いでいる場合には以下の方法で最小全域木を構築できる。

• プリム法
• クラスカル法

これらは辺に向きがあると使えない。

本題

最小全域木に向きがあったらどうするか？
つまりあるノードを根とした時にそこから全てのノードへ移動可能な木を構築した際に必要なコストはいくつか？という問に対してどう回答するか。

有向最小全域木を求めるにはChu-Liu/Edmondのアルゴリズムというのがある。
ここでは強連結成分分解を用いて有向最小全域木を構築する。

基本のアイデア

まず最も理想的でシンプルな有向最小全域木を考えてみる。
各ノードにおいて、そのノードへ流入する辺のうち最も小さいものが選択された場合に最小全域木になっていれば何も難しくない。

Fig1-1において、根であるノード0を除く全てのノードにおいて流入する辺の中で最小コストのものを選ぶ。

• ノード1に流入する辺は0→1を結ぶコスト1の辺のみなのでこれを選ぶ。
• ノード2に流入する辺は1→2を結ぶコスト1の辺もしくは3→2を結ぶコスト10の辺なので低コストな前者を選ぶ。
• ノード3に流入する辺は0→3を結ぶコスト10の辺もしくは2→3を結ぶコスト1の辺なので低コストな後者を選ぶ。

こうして構築されるのがFig1-2のようなグラフになる。
見てみると赤字の辺が採用された辺であり確かに根から辿ることで全ての辺へ移ることが可能である。

ではまず、この方法で生成するグラフが必ず有向最小全域"木"なのか？というところを考える。

全N個のノードのうち根を除くN-1個のノードに対して1つの辺を採用したグラフなのでグラフが連結であれば必ず木になっているし、Fig1-2の通り有効最小全域木になる。
では、グラフが非連結になる場合。これは当然有効最小全域木とは言えない。
ではどういうケースで非連結になるのか？

→ どこかでサイクルが発生している状況である。例えばFig2-1を見てみる。
同様に書くノードの最小コストの辺を選択する。

• ノード1に流入する辺は0→1を結ぶコスト1の辺のみなのでこれを選ぶ。
• ノード2に流入する辺は1→2を結ぶコスト10000の辺もしくは3→2を結ぶコスト1の辺なので低コストな後者を選ぶ。
• ノード3に流入する辺は0→3を結ぶコスト10の辺もしくは2→3を結ぶコスト1の辺なので低コストな後者を選ぶ。

すると構築される新たなグラフはFig2-2のようになる。

サイクルが発生したらどうするか

強連結成分をマージする

2と3を結ぶ辺はいずれのノードから見ても最小コストの辺を選択しているのでどちらかがその辺を諦めて別の辺から流入することにするしかない。
ここで重要なのは2と3の間の辺を両方とも切るケースは考える必要がないことである(Fig2-3少なくとも2か3はコスト最小の辺を選んだら？ってなる)。
→ つまり、ノード2と3は切り離す必要がないなら単一のノードと考えても差し支えない。(Fig2-4の赤いノード)

2と3のように違いに行き来可能な強連結成分を1つにまとめる時には強連結成分分解(SCC)というアルゴリズムが役に立つ。
ここでは説明を割愛。

また、ここで強連結成分を構成する2←→3の辺の合計値2は辺をどちらかの辺を譲ったとしても必ずかかる辺のコストなのであらかじめこの段階でカウントしておき、どちらかの辺に譲った場合に追加でかかるコストで辺のコストを上書きしておく。(Fig2-4の緑の辺)

(Fig2-4の緑の辺について念の為補足的な説明)
元々のグラフでノード0→3のコスト10の辺を選択するとなると元のグラフのノード2→3のコスト1の辺を辞めて変更することになるので差分は9。これが上書き後のノード0→強連結成分2へのコスト9に対応している。

サイクルに属しておらずここで選択された辺は必ず採用してOK

サイクルが発生してしまっている部分でどちらかの辺を譲りましょうという話なのでサイクルに関係していない辺が選ばれないことで得することは起こり得ない。→ サイクルに関わらない辺なら有効最小全域木に使用されると言い切れるのでこの段階でカウントしてしまい、それ以上考慮不要なのでコストを0に上書きする。(Fig2-5)

次は何するの？

実はこの先は同じことを繰り返すだけでいい。
結局、強連結成分をまとめて新たなノードにし、コストを新たな値に直したことで、単にFig2-6のようなグラフが出題されている状況と同値なのだ。(もちろんカウンタsumの値は初期値と異なるが)
つまりはサイクルがないかを探し→あるなら確定させた上で辺のコスト更新とノード縮約を実施。サイクルがなくなった(=木になったら)終了すればいい。

一応Fig2-5から先を実施すると、

• ノード0は根なので無視。
• ノード1に流入する辺は0→1を結ぶコスト0の辺のみなのでこれを選ぶ。
• ノード2に流入する辺は1→2を結ぶコスト9999の辺もしくは0→2を結ぶコスト9の辺なので低コストな後者を選ぶ。

よって、以下の木が構成され、これは有効最小全域木になる。コストは12と分かる。

早くコードを見せろ

verifyに使った問題は以下
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_B&lang=ja

提出
https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=7990028#1

もう少し発展

そもそも構築した木自体が欲しくなったらどうする？

サイクルでない辺を採用する際にはその辺はグラフに取り込んでOK。サイクルは保留しておき、後からあるノードへの別の流入経路(辺)を採用したらそっちで上書くようにしたらいいなじゃないかと思う。