基本情報技術者 予想問題｜A 第19問

解説

最小全域木（MST）とは、グラフのすべての頂点を含み、閉路を持たず、辺の重みの合計が最小となる木である。クラスカル法は辺を重みの小さい順に調べ、閉路ができない辺だけを採用していくことでMSTを構築する貪欲法のアルゴリズムである。同じ目的のものに、頂点を1つずつ木に取り込んでいくプリム法がある。ダイクストラ法は始点から各頂点への最短経路を求めるアルゴリズムであり、「全頂点を最小コストでつなぐ」MSTとは目的が異なる点に注意する。バブルソートは整列、二分探索法はソート済み列からの探索のアルゴリズムである。基本情報ではクラスカル法・プリム法＝最小全域木、ダイクストラ法＝最短経路という対応の判別が頻出である。