最小全域木電卓
クラスカル法またはプリム法を使用して、重み付きグラフの最小全域木（MST）を計算します。インタラクティブなグラフ可視化、アルゴリズムのステップバイステップ追跡、エッジ選択アニメーション機能を備えています。
広告ブロッカーにより広告が表示できません
MiniWebtool は広告収益で無料提供しています。このツールが役に立ったら、Premium（広告なし＋高速）をご利用いただくか、MiniWebtool.com を許可リストに追加して再読み込みしてください。
- または Premium（広告なし）にアップグレード
- MiniWebtool.com の広告を許可してから再読み込みしてください
最小全域木電卓
最小全域木電卓へようこそ。このツールは、クラスカル法またはプリム法を使用して重み付きグラフのMSTを計算するインタラクティブなツールです。グラフ理論の学習、ネットワークインフラの設計、またはリソース配分の最適化など、この電卓は組合せ最適化における2つの基本的なアルゴリズムを視覚的かつステップバイステップで探索する手段を提供します。
最小全域木（MST）とは何ですか？
連結された無向重み付きグラフの最小全域木とは、以下の条件を満たすエッジの部分集合です：
- すべての頂点を接続している（全域）
- サイクルを含まない（木）
- 可能な限り最小の合計エッジ重みを持つ
V個の頂点を持つグラフの場合、MSTは常にちょうど V - 1 本のエッジを持ちます。グラフが非連結の場合、結果は各連結成分ごとのMSTの集合である最小全域森となります。
クラスカル法
クラスカル法は、エッジを重みの昇順で処理することでMSTを構築するエッジベースの貪欲アルゴリズムです。Union-Find（素集合データ構造）を使用して、効率的にサイクルを検出します。
クラスカル法の擬似コード
MST ← 空の集合
すべてのエッジを重み（昇順）でソート
すべての頂点に対してUnion-Findを初期化
for each エッジ (u, v, w) in ソート済みエッジ:
if Find(u) ≠ Find(v): // 異なるコンポーネント
MST ← MST ∪ {(u, v, w)}
Union(u, v) // コンポーネントをマージ
return MST
プリム法
プリム法は、開始頂点からMSTを成長させる頂点ベースの貪欲アルゴリズムです。各ステップで、木の中にある頂点と木の外にある頂点を結ぶ最も安価なエッジを追加します。
プリム法の擬似コード
MST ← 空の集合
inMST ← {start}
PQ ← startからのエッジを含む優先度付きキュー
while PQが空でない and |inMST| < |V|:
(w, u, v) ← PQから最小値を抽出
if v ∉ inMST:
MST ← MST ∪ {(u, v, w)}
inMST ← inMST ∪ {v}
vからのすべてのエッジをPQに追加
return MST
クラスカル法 vs プリム法：どちらを使うべきか？
| 特徴 | クラスカル法 | プリム法 |
|---|---|---|
| アプローチ | エッジベース（グローバルソート） | 頂点ベース（局所的成長） |
| データ構造 | Union-Find | 優先度付きキュー |
| 時間計算量 | \( O(E \log E) \) | \( O((V + E) \log V) \) |
| 適した対象 | 疎なグラフ | 密なグラフ |
| 非連結グラフ | 全域森を生成 | 開始ノードの成分のみ全域化 |
| 並列化 | 比較的容易に並列化可能 | 本質的に逐次的 |
この電卓の使い方
- グラフのエッジを定義：
ノード1, ノード2, 重みの形式でエッジを1行に1つずつ入力します。MSTは無向グラフで動作するため、各エッジは双方向として機能します。 - アルゴリズムを選択： 疎なグラフにはクラスカル法、密なグラフにはプリム法を選択します。どちらも最適なMSTを生成します。
- 開始ノードを設定（プリム法のみ）： オプションでプリム法の開始地点を指定します。これはエッジの選択順序に影響しますが、MSTの合計重みには影響しません。
- MSTを計算： 「MSTを見つける」をクリックしてアルゴリズムを実行します。インタラクティブな可視化、エッジテーブル、ステップバイステップの追跡を探索します。
- ステップを進める： 「次へ」/「前へ」ボタンを使用して、キャンバス上のリアルタイムハイライトと共にアルゴリズムの実行をステップごとに確認します。
結果の理解
MSTエッジテーブル
MSTに選択されたすべてのエッジを、追加された順序、個別の重み、およびMSTの総重みと共に表示します。
グラフ可視化
インタラクティブなキャンバスに、カラーコード化された要素でグラフが表示されます：
- 緑色のノードとエッジ = MSTの一部
- オレンジ色のハイライト = 現在調査中
- グレーの要素 = まだMSTの一部ではない
ステップバイステップ追跡
アルゴリズムの各決定（どのエッジが調査されたか、採用または拒否されたか、その理由、およびMST構築の現在の状態）を表示します。
MSTの現実世界での応用
ネットワーク設計
最も古典的な応用例です。ノード（都市、サーバー、電気機器）を最小限の合計ケーブル、光ファイバー、またはパイプの長さで接続する場合、MSTが最適な解決策を提供します。通信会社はインフラコストを最小限に抑えるためにMSTベースのアルゴリズムを使用しています。
クラスタ分析
機械学習やデータサイエンスにおいて、MSTベースのクラスタリング（単連結法など）は、MSTから最も長いエッジを削除することでデータポイントをグループ化します。これにより、グループ数を事前に指定することなく、自然なクラスターを生成できます。
画像セグメンテーション
コンピュータビジョンのアルゴリズムは、画像を意味のある領域に分割するためにMSTを使用します。ピクセルをノード、エッジの重みを色や強度の差として扱い、MSTのエッジを切断することで異なるオブジェクトを分離します。
近似アルゴリズム
MSTは、距離空間における巡回セールスマン問題（TSP）の2倍近似を提供します。MSTの重みは最適なTSPツアーの下限であり、MSTのエッジを2倍にすることで最適解の2倍以内のツアーが得られます。
回路設計
VLSIチップ設計では、回路基板上のコンポーネントを接続する総配線長を最小化するために（シュタイナー木変種を介して）MSTが使用され、信号遅延と製造コストを削減します。
MSTの主な性質
- カットの性質： グラフの任意のカットにおいて、そのカットを横切る最小重みのエッジはMSTに含まれます。
- サイクルの性質： グラフ内の任意のサイクルにおいて、そのサイクル内で最大重みを持つエッジはMSTに含まれません（重みが一意であると仮定）。
- 一意性： すべてのエッジの重みが異なる場合、MSTは一意に決まります。重みが重複している場合、同じ合計重みを持つ複数の有効なMSTが存在する可能性があります。
- 部分グラフ： MSTは V-1 本のエッジを持ち、サイクルを持たない部分グラフです。
よくある質問
最小全域木（MST）とは何ですか？
最小全域木とは、連結された無向重み付きグラフにおいて、すべての頂点を最小の合計エッジ重みで、サイクルを作らずに接続するエッジの部分集合のことです。V個の頂点を持つグラフのMSTは、ちょうど V-1 本のエッジを持ちます。
クラスカル法とプリム法の違いは何ですか？
クラスカル法はエッジベースのアルゴリズムです。すべてのエッジを重み順にソートし、Union-Findデータ構造を使用してサイクルを作成しないエッジを貪欲に追加していきます。プリム法は頂点ベースのアルゴリズムです。優先度付きキューを使用して、常に既存の木と新しい頂点を結ぶ最も安価なエッジを追加することで、開始ノードからMSTを成長させます。どちらも最適なMSTを生成しますが、エッジの選択順序が異なる場合があります。
クラスカル法とプリム法のどちらを使うべきですか？
クラスカル法は一般的に疎なグラフ（ノードに対してエッジが少ないグラフ）に適しており、時間計算量は O(E log E) です。プリム法は、バイナリヒープを使用した場合、時間計算量 O(E log V) で密なグラフに適しています。非常に密なグラフの場合、プリム法にフィボナッチヒープを組み合わせることで O(E + V log V) を達成します。
1つのグラフに複数の有効なMSTが存在することはありますか？
はい、同じ重みのエッジが存在する場合、1つのグラフに複数の有効なMSTが存在することがあります。異なるMSTは合計重みは同じですが、含まれるエッジが異なる場合があります。クラスカル法とプリム法は同じグラフに対して異なるMSTを生成する可能性がありますが、どちらも同じ最小合計重みを持ちます。
MSTの現実世界での応用例は何ですか？
MSTは、ネットワーク設計（ケーブルや光ファイバーの長さの最小化）、回路基板のレイアウト、クラスタ分析、画像セグメンテーション、系統樹の構築、巡回セールスマン問題（TSP）の近似、および最小コストでの道路・パイプライン・電気ネットワークの構築に使用されます。
MSTは非連結グラフでも機能しますか？
真のMSTには連結グラフが必要です。グラフが非連結の場合、アルゴリズムは各連結成分ごとのMSTの集合である「最小全域森」を生成します。この電卓は、グラフが完全に連結されていない場合にその旨を表示します。
参考資料
このコンテンツ、ページ、またはツールを引用する場合は、次のようにしてください：
"最小全域木電卓"（https://MiniWebtool.com/ja//） MiniWebtool からの引用、https://MiniWebtool.com/
miniwebtool チーム作成。更新日: 2026年2月19日
また、AI 数学ソルバー GPT を使って、自然言語による質問と回答で数学の問題を解決することもできます。