スマートフォン用の表示で見る

最小全域木

サイエンス

最小全域木

さいしょうぜんいきぎ

無向グラフにおける、全ての接点を結合する木のうち、辺の重みの総和が最小な物。木なので、閉路を含まない。英語では、Minimum Spanning Tree。

アルゴリズム一覧

最適分岐

有向グラフの場合は最適分岐といい、アルゴリズムはエドモンズ法などがある。

最適分岐