Chu-Liu/Edmonds' algorithm

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /chu-liu-edmonds#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /chu-liu-edmonds#noredirect を利用してください。
name
Chu-Liu/Edmonds' algorithm
short description
Chu-Liu/Edmonds' algorithm とは、与えられた辺重み付き有向グラフ $G$ と頂点 $r$ に対し、$r$ を根とする最小全域有向木を $O(V E)$ で求めるアルゴリズムである。
input
辺重み $c : V \to \mathbb{R}$ 付き有向グラフ $G = (V, E)$ および頂点 $r \in V$
output
$r$ を根とする最小全域有向木 $T$
time complexity
$O(V E)$