平成26年度 秋期 午前 問4

✓ これが正解エ幅優先探索

解説

添字の区切りが段の区切りと重なります。

設問は、根を先頭に置き、ある要素の左の子をその添字の 2 倍の位置に、右の子を 2 倍に 1 を足した位置に置くという決まりで木を配列に写したとき、その配列を先頭から順に調べる行為が、木のどの探索に当たるかを問うています。見分けの軸は、添字の並びが木のどの単位と一致するかという一点です。要素が 7 個の場合で添字を実際に置いてみます。1 番目が根、2 番目と 3 番目が根の左右の子、4 番目と 5 番目が 2 番目の子、6 番目と 7 番目が 3 番目の子になります。ここで添字を 1、2 から 3、4 から 7 と切ると、その切れ目が根の段、その次の段、さらに次の段という段の境目とそのまま重なります。段が一つ下りるたびに節の数が倍になるので、境目は 2 のべき乗の位置に現れるからです。したがって配列を先頭から順に調べることは、浅い段の節をすべて訪れてから次の段へ移ることと同じであり、これが幅優先探索の訪れ方そのものです。

ほかの選択肢はなぜ違うのか

• ア行きがけ順（先行順）深さ優先探索：この順は節を訪れてから左、右と下りるので、先頭の二つまでは配列の並びと一致します。ところが三つ目で左の子の子へ飛ぶため、同じ段の右側を飛び越してしまい、そこで並びが割れます。
• イ帰りがけ順（後行順）深さ優先探索：この順は左、右と下り切ってから節を訪れるので、根が最後に回ります。配列の先頭は必ず根ですから、出だしの時点で並びが合いません。
• ウ通りがけ順（中間順）深さ優先探索：この順は左、節、右と進むので、いちばん左下の葉が最初に来ます。これも配列の先頭に根が来るという性質と正面から食い違います。