最小全域有向木(Chu-Liu/Edmond)
説明
頂点 $r$ を根とする最小全域有向木を求めるアルゴリズム。頂点 $r$ から全ての頂点への経路が存在する木のうち最小コストのものを求める。
基本的には各頂点に入る辺のうち最小コストの辺を選ぶ。これらの辺からなるグラフが木ならそれが解。それ以外なら有向閉路が含まれているので閉路を縮約して適切に処理して, 閉路がなくなるまで再帰的に呼び出すことを繰り返す。
実装例 1
Skew-Heap が必要
$O(E \log V)$
$V$: 頂点数, $E$: 辺数
実装例 2
強連結成分分解 が必要
$O(VE)$
$V$: 頂点数, $E$: 辺数