アルゴリズムとプログラミング
クラスカル法（Kruskal's Algorithm）による最小全域木の構築手順として正しいものはどれか。
ア.任意の1頂点から出発し、最も近い未訪問の頂点を選択しながら全頂点を連結する。
イ.全辺をコストの昇順でソートし、閉路を形成しない辺を順に選択して全頂点を連結する。正解
ウ.全頂点間の最短経路を求め、その中から全頂点を連結できる辺を選択する。
エ.再帰的にグラフを分割し、各部分グラフの最小コスト辺を選択して統合する。
解説
クラスカル法は「安い材料から使う材料節約型の大工」。橋を最安値順に架けていき、島が繋がってしまう橋は飛ばすというグリーディ戦略です。
なぜ イ が正解か
クラスカル法のアルゴリズム: ① 全辺をコストの小さい順にソート ② 辺を順に取り出す ③ その辺を追加すると閉路ができる → 捨てる 閉路ができない → 最小全域木に追加 ④ V-1本（Vは頂点数）の辺が選ばれたら完成 閉路の検出にはUnion-Find（素集合データ構造）を使います。グリーディ法の代表例で、「局所最適な選択が全体最適をもたらす」アルゴリズムです。
出典: AI生成問題（学習用）