最小全域木（クラスカル法・プリム法）とは？
最小全域木（クラスカル法・プリム法）とは、重み付きの連結グラフから、すべての頂点をつなぎつつ辺の重みの合計が最小になるように辺を選んだ木。閉路を作らないので、頂点数がn個なら選ばれる辺はn−1本になる。
さいしょうぜんいきぎ
最小全域木（クラスカル法・プリム法）の意味
重み付きの連結グラフから、すべての頂点をつなぎつつ辺の重みの合計が最小になるように辺を選んだ木。閉路を作らないので、頂点数がn個なら選ばれる辺はn−1本になる。
最小全域木（クラスカル法・プリム法）の具体例
複数拠点を通信回線で結ぶときの敷設費用の最小化。クラスカル法は重みの小さい辺から順に、閉路ができないものだけを採用する。プリム法は1つの頂点から始めて、木に接する最小の辺を足していく。
最小全域木（クラスカル法・プリム法）は試験でどう引っ掛けられる？
最小になるのは「全体の合計」であって、特定の2頂点間の経路が最短になるわけではない。最短経路問題の答えと同じものだと思い込む誤りが典型的な引っ掛けになる。
最小全域木（クラスカル法・プリム法）と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。