平成27年度 III-11

解説

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

同じ木に対する、深さ優先探索と幅優先探索の、探索順序の違いを追う問題。

解き方

① 深さ優先: 左の枝を行き止まりまで進んでから戻る。幅優先: 同じ深さを左から全部調べてから次の深さへ
② 深さ優先: S→1番目の子とその下2つ→2番目の子、その左の子とさらに下の1つ、右の子→3番目の子→G で10個。幅優先: S(1)+深さ1の4個+深さ2のGまでの5個=10個
③ 深さ優先10、幅優先10(⑤)

正解が正しい理由

木は、Sの下に4つの子(左から、子1、子2、子3、子4)がある。子1は2つの子を持ち、子2は2つの子(左の子は、さらに1つの子を持つ)を持ち、子3の子がG、子4は3つの子を持つ。深さ優先探索は、左の枝の奥まで先に調べる。S、子1、子1の左の子、子1の右の子、子2、子2の左の子、その下の子、子2の右の子、子3、Gの順で、10個のノードを調べる。幅優先探索は、深さごとに、左から調べる。S、子1、子2、子3、子4(深さ1の4個)、続いて深さ2で、子1の2つの子、子2の2つの子、Gの順で調べ、Sを含めて1+4+5=10個のノードを調べる。したがって、深さ優先探索10、幅優先探索10で、⑤が正しい。

各選択肢について

• ① 深さ優先9、幅優先9は、どちらも数え方が1つ少ない。
• ② 深さ優先9は、子2の左の子の下のノードを数え落とした場合などの値。
• ③ 幅優先11は、Gの調査後もさらに1つ調べた場合などの値。
• ④ 幅優先9は、数え方が1つ少ない値。
• ⑤ 深さ優先探索10、幅優先探索10で、正しい。これが正答。

覚えるべきポイント

深さ優先探索=スタックを使い、枝の奥まで進んでから戻る。幅優先探索=キューを使い、浅い階層から順に調べる。調べたノード数は、目的ノードに至るまでに、訪問したノード数(開始と目的を含む)。