最小全域ネットワーク
無向の接続候補と費用から、全体を結ぶ最小費用の辺、または分離した最小全域森を求めます。
例の値が入力されています。直接確認するか、値を変更してみてください。
入力はブラウザで処理されます。再読み込みすると例の値に戻ります。
使い方と例
Kruskal: 費用の昇順で、異なる連結成分を結ぶ辺のみを選択します。
既定の4ノードでは辺の行1,2,3を選び、総費用6、連結成分1個です。
2〜50ノード・最大200辺、整数費用0〜1,000,000です。自己ループは拒否し、並行辺は許容します。実施設計の適合性は評価しません。 浮動小数点の結果は最大有効数字12桁で表示します。
よくある質問
接続候補が分離していると失敗しますか?
各成分の最小森と成分数を返します。成分数が1より大きければ全体は接続されていません。
最小全域木と最短経路は同じですか?
いいえ。全ノードを結ぶ辺の総費用を最小化し、特定の始点と終点間の距離を最小化する問題とは異なります。
計算基準と参考資料
- SciPy: minimum spanning trees and forests
Kruskal法と最小全域木・森。