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

Wikipedia内リンクを1点修正: 「連結」→「連結グラフ」。Wikipedia内リンクを3点追加: 「重み」「ノード」「線形」。
編集の要約なし
(Wikipedia内リンクを1点修正: 「連結」→「連結グラフ」。Wikipedia内リンクを3点追加: 「重み」「ノード」「線形」。)
{{著作権問題調査依頼}}
{{Wikify|date=2017年8月1日 (火) 10:25 (UTC)}}
'''ブルーフカ法'''とは、[[グラフ理論]]で[[ウェイト (表現論)|重み]]付き[[連結グラフ|連結]]グラフの最小[[全域木]]を求める[[最適化問題]]の[[アルゴリズム]]である。
 
== 概要 ==
 
== アルゴリズムの解説 ==
このアルゴリズムではまず、頂点ひとつの[[木 (数学)|木]]を全ての[[頂点 (グラフ理論)|ノード]]について作成し、それぞれ全ての木について、重みが最小の辺を探索する。この際、選ばれる辺は重複しても良い。選択された辺で繋がれた木は森(木の集合)に追加する。次に、重みが最小の辺を探索するという手順を、全ての森についても行う。これを森がひとつの木になるまで繰り返す。一つの木になったらそれが最小全域木だ。
 
== 例 ==
 
== 計算量 ==
辺の数をE、Vを頂点の数として、ブルーフカ法は{{math|''O''(log ''V'')}}回の反復をするため、計算には時間{{math|''O''(''E'' log ''V'')}}かかる。[[平面グラフ]]では、反復するごとにふたつの木の間で重みが最小の辺以外を取り除くことにより、より[[線型性|線形]]に近い計算量で済む。
 
== その他のアルゴリズムとの比較 ==
472

回編集