出典：公益社団法人 日本技術士会「技術士第一次試験 過去問題」
隣接行列で表された有向の木構造で、ノード0から始める深さ優先探索を行うPythonプログラムの、再帰呼出しの空欄アに入るプログラム片として、実行結果(ノードと深さ)から最も適切なものを選ぶ問題。
深さ優先探索の再帰呼出しの引数を、実行結果から決める問題。
① 深さ優先探索の再帰: ノードiの子を調べるには隣接行列のi行目(mm[i])を渡し、1段深くなるので深さはd+1
② 実行結果で子の深さが親より1大きい → d+1 で③④。i行目を渡すのは③
③ tsearch(mm[i], d+1)(③)
関数tsearch(l, d)は、隣接行列の1行l(あるノードの子への辺の有無)を受け取り、辺があるノードiについて、そのノード番号と深さdを表示し、そのノードの子を再帰的に調べる。ノードiから先の子を調べるには、ノードiに対応する行mm[i]を渡す必要があり、深さは1つ深くなるので、d+1とする。したがって、空欄アは tsearch(mm[i], d+1) である。実行結果は、ノード0(深さ0)、ノード1(深さ1)、ノード3(深さ2)、ノード4(深さ2)、ノード2(深さ1)、ノード5(深さ2)、ノード7(深さ3)、ノード8(深さ3)、ノード6(深さ2)となり、一致する。したがって③が正しい。
深さ優先探索は、再帰呼出しで、行きがけに、子ノードを順に調べる。隣接行列では、ノードiの行が、iから出る辺を表し、再帰呼出しでは、深さを+1する。
キーワード: 深さ優先探索、隣接行列、再帰呼出し、木構造、Python、グラフ探索、情報工学部門