基本情報技術者試験基礎・応用
条件を読む・根拠を説明する
幅優先探索の待ち行列
条件を整理し、答えを選んでから解き方を確認しましょう。
有向辺はA→B,A→C,B→D,C→E。Aからキューで幅優先探索し、隣接点は記載順、登録時に訪問済みとする。取出し順はどれか。
答え・解き方を読む
A,B,C,D,E
図で見る
親子の接続と訪問順を分けて追う
図を拡大して見る ↗辺A→B,A→C,B→D,C→Eに限定した図です。記載順で幅優先はA,B,C,D,E、深さ優先はA,B,D,C,Eとなります。
図は問題の関係を整理する模式図です。記号には各問題の数値を当てはめます。寸法・面積・時間の縮尺や、実施工の全条件は表していません。
考える順序
- 1AからB,Cをこの順でキューへ登録
- 2Bを取出してDをCの後へ登録
- 3Cの後にD,Eを取り出す
選択肢ごとの理由
- 正解 · A,B,C,D,E
AからB,Cをこの順でキューへ登録。Bを取出してDをCの後へ登録。Cの後にD,Eを取り出す。
- 比較 · A,B,D,C,E
Bの子Dより、先に登録済みのCを取り出します。
- 比較 · A,C,E,B,D
隣接点の登録順はB,Cと指定されています。
- 比較 · D,B,A,C,E
開始点Aが最初に処理されます。