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