「ブルーフカ法」の版間の差分

m
最小全域木へのリンクを追加しました
(Wikipedia内リンクを1点修正: 「連結」→「連結グラフ」。Wikipedia内リンクを3点追加: 「重み」「ノード」「線形」。)
m (最小全域木へのリンクを追加しました)
{{著作権問題調査依頼}}
{{Wikify|date=2017年8月1日 (火) 10:25 (UTC)}}
'''ブルーフカ法'''とは、[[グラフ理論]]で[[ウェイト (表現論)|重み]]付き[[連結グラフ]]の最小[[全域木#最小全域木|最小全域木]]を求める[[最適化問題]]の[[アルゴリズム]]である。
 
== 概要 ==
 
== アルゴリズムの解説 ==
このアルゴリズムではまず、頂点ひとつの[[木 (数学)|木]]を全ての[[頂点 (グラフ理論)|ノード]]について作成し、それぞれ全ての木について、重みが最小の辺を探索する。この際、選ばれる辺は重複しても良い。選択された辺で繋がれた木は森(木の集合)に追加する。次に、重みが最小の辺を探索するという手順を、全ての森についても行う。これを森がひとつの木になるまで繰り返す。一つの木になったらそれが[[全域木#最小全域木|最小全域木]]だ。
 
== 例 ==
3

回編集