最小全域ネットワーク

無向の接続候補と費用から、全体を結ぶ最小費用の辺、または分離した最小全域森を求めます。

例の値が入力されています。直接確認するか、値を変更してみてください。

入力はブラウザで処理されます。再読み込みすると例の値に戻ります。

結果

使い方と例

Kruskal: 費用の昇順で、異なる連結成分を結ぶ辺のみを選択します。

既定の4ノードでは辺の行1,2,3を選び、総費用6、連結成分1個です。

2〜50ノード・最大200辺、整数費用0〜1,000,000です。自己ループは拒否し、並行辺は許容します。実施設計の適合性は評価しません。 浮動小数点の結果は最大有効数字12桁で表示します。

よくある質問

接続候補が分離していると失敗しますか?

各成分の最小森と成分数を返します。成分数が1より大きければ全体は接続されていません。

最小全域木と最短経路は同じですか?

いいえ。全ノードを結ぶ辺の総費用を最小化し、特定の始点と終点間の距離を最小化する問題とは異なります。

計算基準と参考資料

計算基準の確認: · 計算・検証原則 · エラー報告