Prim または Kruskal を実行する方法
- 01重み付きグラフを構築する。グリッドのプリセット(rows 4, cols 5 — 20 ノード、31 本の単位辺)、ランダム連結グラフ、または Complete K₆ を試します。
- 02Prim を選んで Source を設定するか、ソース不要の Kruskal に切り替えます。
- 03テーブルを読む。まず総重み、次に選択辺、成分、森かどうか。その下に選択辺ごとの重みの行が並びます。
- 04もう一方のアルゴリズムで照合する— 同じグラフなら総重みが一致するはずです。
- 05実行を 1 ステップずつ進めるには Play / Prev / Next。Prim は成長するフロンティアを、Kruskal は採用辺と却下辺を強調します。
ワーク例
パネルが表示する値:
| グラフ · アルゴリズム |
読み取り |
| グリッド 4 × 5、1-1 から Prim |
総重み 19、選択辺 19 / 31、成分 1、森か No |
| グリッド 4 × 5、Kruskal |
総重み 19、選択辺 19 / 31 |
| ランダム連結(n 6、p 0.3、seed 20260730、最大重み 9)、A から Prim |
総重み 16、選択 A–B(3), A–C(4), C–E(2), A–D(6), D–F(1)、選択辺 5 / 7 |
| 同じグラフ、Kruskal |
総重み 16、同じ 5 本の辺を重み順に: D–F(1), C–E(2), A–B(3), A–C(4), A–D(6) |
| Complete K₆、Prim |
総重み 5、選択辺 5 / 15、辺 A–B(1), A–F(1), A–E(1), A–D(1), A–C(1) |
グリッドの MST は 20 ノードに対して 19 本の単位辺 — 理論上の最小 — で、両方のアルゴリズムがそれを達成します。ランダムグラフでは 1 本の辺で答えを手で確認できます。D–F は重み 1 でグラフ内で最も軽いため、どの MST も必ず含み、両方の実行が含んでいます。
2 つのリストが異なる理由
Prim と Kruskal は辺を異なる順序で選び、同点のときは異なる有効な木を選ぶことがあります。Kruskal はすべての辺を大域的に並べ替えるので、そのテーブルはどこであれ最も軽い辺から始まります。Prim は成長する 1 本の木のフロンティアだけを見るので、そのテーブルは根から最初に出るものから始まります。ランダムグラフでは両者が同じ集合を生みます — そこの最小全域木は一意です — が、K₆ のリスト(すべて重み 1)は多くの完全木の 1 つにすぎません。重みが繰り返すときは、辺リストではなく総重みと辺数を比較してください。
限界
- 非連結グラフは森を与えます。
- 森かどうかの行が Yes になり、成分数は 1 より大きいままです。答えは最小全域森、成分ごとに 1 本の木であり、単一の木ではありません。
- 無向辺のみ。
- Prim は有向グラフを無向として扱い、警告でそう告げます。Kruskal の成分併合も無向の考え方です。どちらも有向最小有向木は解きません。
タイブレークの落とし穴
Complete K₆ ではすべての辺が 1 なので、どの全域木も 5 です。Prim はたまたま A を中心とする星で答えます: A–B, A–F, A–E, A–D, A–C。このリストはある最小木であってその最小木として読んでください。等重みのグリッドにも同じ注意が当てはまります。グリッドの答え 19 は安定していますが、どの 19 本の単位辺が現れるかは Prim と Kruskal で異なることがあり、両方とも正しいままです。
役立つ場面
最も安い配線という主張を確認する
ランダムグラフでは最も重い 2 本、E–F(8) と B–D(7) はどちらも除外され、A–D(6) が採用されます。提案されたネットワークも同じように確認してください。E–F(8) に払いながら安い D–F(1) を外していれば、最小ではありません。
カットの性質を教える
グリッドはカットの推論を見えるようにします。すべての単位辺は重み 1 のカットを横切り、両アルゴリズムはサイクルを 1 つも作らず 31 本のうち 19 本を採用します。ランダム連結グラフに切り替えて両方を実行すると、ステップ再生が Kruskal の E–F(8) のスキップ(両端がすでに結ばれているため)を示します。
プライバシー
グラフの編集と 2 つの MST 実行はブラウザー内でローカルに実行されます。何もアップロードされません。
参考文献
- Wikipedia, Prim's algorithm, en.wikipedia.org (访问日期:2026-10-07)— 根からのフロンティアの成長。
- Wikipedia, Kruskal's algorithm, en.wikipedia.org (访问日期:2026-10-07)— union-find による重み順。
- Wikipedia, Minimum spanning tree, en.wikipedia.org (访问日期:2026-10-07)— カットとサイクルの性質、重みが異なれば一意。
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022, mitpress.mit.edu (访问日期:2026-10-07)— MST アルゴリズムとカットの性質。
Calculators in this hub
Hand-picked tools, one click away. The mini versions compute live and carry your values into the full calculator.
Sources & review
- Updated