アルゴリズムの解説
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/12/05 08:32 UTC 版)
このアルゴリズムでは1つの辺から始めて、全頂点を覆うようになるまで連続的に木の大きさを拡大していく。 入力: 重み付きグラフ（頂点集合 V、辺集合 E） 出力: Vnew と Enew が最小全域木を表している。 Vnew = {x}、ここで x は V の元であり、任意のノード（出発点）Enew = {}while (Vnew ≠ V) Vnew に含まれる頂点 u と 含まれない頂点 v を結ぶ重みが最小の辺 (u, v) を E から選択（同じ重みの辺が複数あるときは、どちらを選んでも良い） v を Vnew に加える (u, v) を Enew に加える
※この「アルゴリズムの解説」の解説は、「プリム法」の解説の一部です。
「アルゴリズムの解説」を含む「プリム法」の記事については、「プリム法」の概要を参照ください。
アルゴリズムの解説
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/15 15:56 UTC 版)
このアルゴリズムではまず、頂点ひとつの木を全てのノードについて作成し、それぞれ全ての木について、重みが最小の辺を探索する。この際、選ばれる辺は重複しても良い。選択された辺で繋がれた木は森（木の集合）に追加する。次に、重みが最小の辺を探索するという手順を、全ての森についても行う。これを森がひとつの木になるまで繰り返す。一つの木になったらそれが最小全域木だ。
※この「アルゴリズムの解説」の解説は、「ブルーフカ法」の解説の一部です。
「アルゴリズムの解説」を含む「ブルーフカ法」の記事については、「ブルーフカ法」の概要を参照ください。
アルゴリズムの解説
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/10 17:55 UTC 版)
クラスカル法の手順は次の通り。 グラフの各頂点がそれぞれの木に属するように、森（木の集合） F を生成する（つまり頂点1個だけからなる木が頂点の個数だけ存在する）S ← グラフの全ての辺を含む集合while (S が空集合ではない) S から重みが最小の辺 e を削除する if (e が2つの木を連結するもの) e を森に加え、2つの木を1つにまとめる このアルゴリズムが終了した時点で、森は単一の木となっており、元のグラフの最小全域木になっている。
※この「アルゴリズムの解説」の解説は、「クラスカル法」の解説の一部です。
「アルゴリズムの解説」を含む「クラスカル法」の記事については、「クラスカル法」の概要を参照ください。
- アルゴリズムの解説のページへのリンク
