令和6年度 III-5

解説

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

木構造での深さ優先探索と幅優先探索で、目的ノードGまでに調べるノード数を求める問題。

解き方

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

正解が正しい理由

木は、Sの子が4つ(左からc1〜c4)。c1の子は2つ(葉)。c2の子は2つで、左の子には葉の子が1つ、右の子は葉。c3の子は1つで、その子は2つの葉を持つ。c4の子は3つで、左端がGである。深さ優先探索は、左の枝を深く進むので、S(1)、c1(2)、その子2つ(3、4)、c2(5)、c2の左の子(6)とその子(7)、c2の右の子(8)、c3(9)、c3の子(10)とその2つの子(11、12)、c4(13)、G(14)の順で、14個のノードを調べる。幅優先探索は、深さごとに左から調べるので、S(1)、第1層の4つ(5)、第2層の左から6番目にGがある(6個)ので、1+4+6=11個のノードを調べる。したがって深さ優先探索14、幅優先探索11の③が正しい。

各選択肢について

• ① 深さ優先探索を12としている点が誤り。
• ② 深さ優先探索を13としている点が誤り。
• ③ 深さ優先探索14、幅優先探索11で、これが正答。
• ④ 深さ優先探索13、幅優先探索12としている点が誤り。
• ⑤ 幅優先探索を12としている点が誤り。

覚えるべきポイント

深さ優先探索は、左の枝を行き止まりまで進んでから戻る(スタック)。幅優先探索は、同じ深さのノードを左から順に調べてから、次の深さへ進む(キュー)。調べたノード数は、探索順に数える。