クラスカル法で、重み付き無向グラフの最小全域木を求める手順として適切なものはどれか。

解説

正解は「重みの小さい辺から順に、閉路ができない場合だけ採用する」です。クラスカル法は、辺を重みの小さい順に調べ、採用しても閉路ができない辺を加えていく貪欲法で、頂点数を V とすると V−1 本の辺を採用した時点で最小全域木が完成します。閉路の判定には素集合データ構造（Union-Find）を使います。「始点から近い頂点から順に、最短距離を確定する」はダイクストラ法の説明で、最短経路木は最小全域木と一致するとは限りません。「重みの大きい辺から順に、すべての辺を採用する」と閉路ができ、木になりません。「任意の頂点から深さ優先探索を行い、たどった辺を採用する」と全域木は得られますが、重みの合計が最小とは限りません。