令和元年度 III-5

解説

この問題で問われていること

探索木を深さ優先・幅優先で探索したとき、Gに到達するまでに調べるノード数の組合せを選ぶ問題。

解き方

① 深さ優先=左の枝を下まで調べてから戻る、幅優先=浅い段から左から順に調べる。個数はSとGを含める
② 深さ優先: S→1段目左→その子2つ→1段目2番目→その子(その下も)→…→1段目3番目→G で10個。幅優先: S、1段目4個、2段目を左から数えてGが5個目 → 1+4+5=10個
③ ④

正解が正しい理由

図の木で、Sの子は左から4つ、Gは3番目の子の下にある。深さ優先探索では、S、1番目の子とその子2つ、2番目の子とその子(さらにその子)ともう1つの子、3番目の子、Gの順に調べ、Gまでで10個。幅優先探索では、S(1個)、1段目の4個、2段目を左から調べてGが5個目となり、1+4+5=10個。したがって④が正しい。

各選択肢について

• ① 深さ優先・幅優先ともに9個ではない。
• ② 深さ優先9個ではない。
• ③ 幅優先9個ではない。
• ④ 深さ優先10個、幅優先10個で、これが正答。
• ⑤ 深さ優先11個ではない。

覚えるべきポイント

深さ優先は左の部分木を全部調べてから右へ、幅優先は1段ずつ左から。個数を数えるときは、開始ノードと目的ノードを含めるかを問題文で確認する。