下図は,探索対象のグラフ(木構造)を表している。開始ノードSから始めて,目的ノードGを深さ優先探索と幅優先探索で探したとき,調べるノードの個数はそれぞれいくつか。ただし,あるノードからその先のノードを調べる際には,左側の枝から先に調べるものとし,ノードの個数には開始ノード及び目的ノードを含めることにする。
① 深さ優先探索9,幅優先探索9
② 深さ優先探索9,幅優先探索10
③ 深さ優先探索9,幅優先探索11
④ 深さ優先探索10,幅優先探索9
⑤ 深さ優先探索10,幅優先探索10
答え
⑤
解説
XXX
① 深さ優先探索9,幅優先探索9
XXX
② 深さ優先探索9,幅優先探索10
XXX
③ 深さ優先探索9,幅優先探索11
XXX
④ 深さ優先探索10,幅優先探索9
XXX
⑤ 深さ優先探索10,幅優先探索10
XXX