アルゴリズムとプログラミング
4頂点グラフにプリム法で最小全域木を求める。辺の重みは A-B=2, A-C=4, A-D=7, B-C=1, B-D=5, C-D=3 とする。最小全域木の総コストはどれか。
ア.5
イ.4
ウ.7
エ.6正解
解説
プリム法は「島をつなぐ橋を最安値で建設する」アルゴリズム。すでに接続された島から最も安い橋を選び続ける。
なぜ エ が正解か
Aから開始。接続可能な辺: A-B=2, A-C=4, A-D=7。最小: A-B=2を選択。{A,B}から接続可能: A-C=4, A-D=7, B-C=1, B-D=5。最小: B-C=1を選択。{A,B,C}から接続可能: A-D=7, B-D=5, C-D=3。最小: C-D=3を選択。総コスト=2+1+3=6。
出典: AI生成問題（学習用）