
木・グラフと幅優先探索
用語の意味
グラフは頂点と辺で関係を表します。木は連結で閉路のない無向グラフで、根を決めると親子関係を表せます。幅優先探索は始点に近い層から順に調べます。深さ優先探索は進める方向に進み、行き止まりで戻ります。
使いどころと問題の見方
幅優先探索ではキューに次の候補を入れます。全ての辺の重みが同じ場合、初めて到達した経路の辺数が最小です。頂点をキューに入れた時点で訪問済みと記録すると、複数の経路から同じ頂点を何度も追加するのを防げます。
確認問題【オリジナル】
辺の長さがすべて等しい地図で、出発点から通る辺の本数が最小の経路を探す方法はどれですか。
ア.挿入ソート
イ.二分探索
ウ.連結リストの末尾への追加
エ.幅優先探索
正解と理由
正解はエです。幅優先探索では、辺を1本でたどれる頂点から順に調べるためです。