JavaScript
 Computer >> コンピューター >  >> プログラミング >> JavaScript

JavaScriptで学ぶ最小全域木（MST）とは？定義・特徴・代表アルゴリズムを解説

最小全域木（MST）とは

最小全域木（Minimum Spanning Tree：MST）または最小重み全域木とは、連結された重み付きグラフ（有向・無向いずれも可）において、すべての頂点を接続する辺の部分集合のうち、サイクル（閉路）を一切含まず、かつ辺の重みの合計が最小となるものを指します。

言い換えると、グラフ内のすべての頂点をカバーする全域木の中で、「辺の重みの総和が可能な限り小さくなる木」のことです。

MSTの主な特徴

  • 全頂点を接続： グラフ内のすべての頂点が必ず含まれ、互いにつながっています。
  • サイクルなし： 閉路が存在しないため、木構造として成立します。
  • 辺の数： 頂点数を V とすると、辺の数は常に「V − 1」となります。
  • 最小コスト： 辺の重みの合計が、取り得る全域木の中で最小です。

代表的なアルゴリズム

MSTを求める代表的なアルゴリズムには、クラスカル法（Kruskal's algorithm）とプリム法（Prim's algorithm）があります。どちらも貪欲法に基づいており、JavaScriptでは配列、ソート、優先度付きキューなどを組み合わせて効率的に実装できます。

MSTの応用例

最小全域木は、電話網や光ファイバー網などのネットワーク設計における配線コストの最適化、データ分析におけるクラスタリング、コンピュータビジョンでの画像セグメンテーションなど、幅広い分野で実用化されています。

  1. クラスカル法による最小全域木（MST）アルゴリズム ― C++での貪欲法の実装

    最小全域木（MST）とは？ 全域木（spanning tree）とは、連結かつ無向のグラフにおいて、すべての頂点を接続する部分グラフのことです。ひとつのグラフには複数の全域木が存在しえますが、その中で辺の重みの合計が他のどの全域木よりも等しいか小さくなるものを最小全域木（Minimum Spanning Tree：MST）と呼びます。各辺には重みが割り当てられており、それらの総和がその全域木の重みとなります。頂点数を V とすると、最小全域木に含まれる辺の数は必ず (V − 1) 本になります。 クラスカル法で最小全域木を求める手順 すべての辺を、重みの昇順（非降順）に並べ替えます。 重み

  2. データ構造入門：最小全域木（Minimum Spanning Tree）とは

    全域木（スパニングツリー）とは全域木（スパニングツリー）とは、無向グラフの部分集合であり、グラフ内のすべての頂点を最小限の数の辺で接続した木構造のことを指します。グラフ内のすべての頂点が互いに連結されている場合、必ず少なくとも1つの全域木が存在します。また、1つのグラフに対して、複数の全域木が存在することもあります。最小全域木（MST）とは最小全域木（Minimum Spanning Tree：MST）とは、連結された重み付き無向グラフにおいて、すべての頂点を接続しながら、辺の重みの合計が最小となるような辺の部分集合です。MSTを求めるアルゴリズムとしては、プリム法（Prims algorit