令和3年度 秋期 応用情報技術者試験 午後 問題 問3 強連結な有向グラフにおける一筆書きの経路を求めるアルゴリズム

【問題の本文・図表】の「図4 関数 directedE のプログラム」における条件分岐 if ( current[x] が ア でない ) を考える。

current[x] には表2で「点 n を始点とする未探索の辺の中で最小の番号を格納する。点 n を始点とする未探索の辺がない場合は 0 を格納する」と定められている（n を x に当てはめる）。
この if 文の条件を満たす場合（真の場合）の処理を見ると、temp ← current[x] として点 $x$ からたどる接続辺を取得し、さらにその先の探索を進めている。
一方、else 側（偽の場合）では、未探索の辺がないと判断して探索済の辺を遡る処理を行っている。

したがって、この if 文は「点 $x$ を始点とする未探索の辺が存在する場合」に探索を進めるための条件である。
未探索の辺がない場合は current[x] に $0$ が格納されるため、「current[x] が $0$ でない」場合が探索を進める条件となる。
よって、アには $0$ が入る。

高得点のポイント

• 未探索の辺が存在しない状態を示す配列 current の値を正確に理解していること。
• プログラムの条件式として適切な形式で記述されていること。

【問題の本文・図表】の「図4 関数 directedE のプログラム」において、current[x] ← イ は「点 $x$ から次にたどる未探索の辺を格納」する処理である。

直前の処理で temp ← current[x] として現在の接続辺を変数 temp に取得している。
「図3 図1のグラフの場合の配列 edgefirst, edgenext」および本文「edgenextによって、辺2の次の接続辺が辺5であることが分かる」とあるように、ある辺 $m$ の次の接続辺の番号は配列 edgenext[m] に格納されている（表2）。
今、たどろうとしている辺は temp に格納されているため、点 $x$ から次にたどる未探索の辺（次の接続辺）は edgenext[temp] となる。
したがって、イには edgenext[temp] が入る。

高得点のポイント

• 配列 edgefirst と配列 edgenext の関係を例示した図3を参考に、点 $x$ から次にたどる未探索の辺の求め方を正確に理解していること。
• 配列 edgenext と変数 temp を用いて、代入文の右辺として適切な構文で記述されていること。

【問題の本文・図表】の「図4 関数 directedE のプログラム」の else 側は、未探索の辺が存在せず探索済の辺を遡る処理である。

配列 searched には「探索済の辺の番号を順番に格納」（表2）し、変数 top はその「探索済の経路の辺の格納位置」（図4）を表している。
探索を進める際は、辺を配列に登録した後に top ← top + 1 と加算して、次に格納すべき位置を指している。
遡る際は、直前に探索済として登録した辺を取り出す必要がある。top は次に格納する空き位置（最新の位置の次）を指しているため、直前に登録された辺の位置は top - 1 となる。
実際、ウの直後の処理で temp ← searched[top] として辺を取り出しているため、取り出す前に top の値を $1$ 減らしておく必要がある。
よって、ウには top - 1 が入る。

高得点のポイント

• 探索済の辺を遡る際の、配列のインデックス（ポインタ）である top の更新ルールを理解していること。
• 数式として適切な形式で記述されていること。

【問題の本文・図表】の「図4 関数 directedE のプログラム」の else 側において、探索済の辺を遡り、その辺 temp を確定済にした後、現在の点 $x$ を更新する処理が x ← エ である。

〔一筆書きの経路を求める手順〕の説明に「終点 $a$ から辺 $4$ を遡ると、辺 $4$ の始点 $d$ で未探索の辺 $7$ が接続している」とあるように、辺を遡るということは、その辺の「終点」から「始点」へと戻ることを意味する。
遡った辺の番号は変数 temp に格納されており、表2の定義より、辺 $m$ の始点の番号は配列 start[m] に格納されている。
したがって、辺 temp を遡った後の現在の点 $x$ は start[temp] となる。
よって、エには start[temp] が入る。

高得点のポイント

• 探索済の経路を遡る際に、遡った辺の始点へと現在の点 $x$ を戻す論理を正確に理解していること。
• 配列 start と変数 temp を用いて、代入文の右辺として適切な構文で記述されていること。

【問題の本文・図表】の「図4 関数 directedE のプログラム」の while ループ内で if ( current[x] が 0 でない ) という判定が行われる。

図2と「一筆書きの経路を求める手順」にあるように、グラフの探索において、全ての辺は「未探索」から一度「探索済」になり、その後「未探索の辺が接続する点まで遡る」過程で「確定済」となる。

• if 文の条件を満たす側は、辺を「未探索」から「探索済」にして配列 searched に登録する処理である。すべての辺が一度ずつたどられるため、この処理はグラフの辺の数（$M$ 回）だけ実行される。
• if 文の else 側は、辺を遡って「探索済」から「確定済」にして配列 path に登録する処理である。すべての探索済の辺が必ず一度ずつ遡られるため、この処理もグラフの辺の数（$M$ 回）だけ実行される。

while ループの中では、この if 判定の後、必ず上記のどちらかの処理が行われる。
したがって、if 文が実行される総回数は、「探索を進める回数」$M$ 回と「遡る回数」$M$ 回の合計である $2M$ 回となる。
図1のグラフにおいて辺の個数 $M$ は $8$ であるため、$8 \times 2 = 16$ 回実行される。
よって、実行回数は $16$ となる。

各選択肢の解説

※本問は数値入力形式のため、選択肢はありません。while ループの実行回数は辺の数の $2$ 倍となるため、これ以外の数値は誤りとなります。

一筆書きができない強連結な有向グラフで関数 directedE を動作させた場合を考える。

強連結であるため、どの点から出発しても必ず他の全ての点に到達する経路が存在するが、一筆書きができない（オイラー閉路を持たない）場合、全ての辺を1回ずつ通って出発点に戻ることはできない。
プログラム（図4）の動作において、

• 条件を満たす側で探索を進め、進めなくなったら else 側で遡る。
• 遡る処理（else 側）が実行されるたびに変数 last が $1$ ずつ減少し、last が $0$ になった時点（last が 1 以上 を満たさなくなった時点）で while ループは終了する。

このアルゴリズムでは、未探索の辺が残った状態で行き止まりになった場合でも、直前の点へとどんどん遡って配列 path に辺を格納していく。一度たどられた辺は必ずいつかは遡られるため、変数 last は確実に減少していく。したがって、無限ループに陥ることはなく、探索は必ず完了する。
強連結なので全ての辺が1回ずつ探索済になり、遡るたびに確定済となって配列 path に全 $M$ 本が格納され、last が $0$ になって終了する（未探索の辺が残ったまま終了することはない）。しかし一筆書きができないグラフでは入る辺と出る辺の数が等しくない点があるため、path に並んだ辺は出発点に戻る閉じた経路にならない（ある辺の終点と次の辺の始点が一致しない箇所ができる、又は最後の辺が出発点に戻らない）。
よって、探索は完了するが、配列 path に格納された経路は一筆書きの経路にはならない。

各選択肢の解説

• ア: 正解。たどった辺の数だけ必ず遡りが行われて last が $0$ になるため探索は完了するが、一筆書きの経路にはならない。
• イ: 関数 directedE では、遡るたびに last が確実に減少して終了条件を満たすため、探索が完了せずに異常終了することはない。
• ウ: 上述の通り、一度たどった辺は有限であり、行き止まりになれば else 側で last が減少するため、無限ループに陥ることはない。

【問題の本文・図表】の「図4 関数 directedE のプログラム」における配列 searched と配列 path の利用状況を考える。

配列 searched はインデックス $1$ から順番に（top を増やしながら）辺を格納していく。
配列 path はインデックス $M$ から逆順に（last を減らしながら）辺を格納していく。
これらを一つの配列（例えば searched を path に置き換える）で共有する場合、配列の前方からは探索済の経路が、後方からは確定済の経路が伸びてくる形になる。

前方から伸びる top（探索済の辺を格納する次の位置）と後方から伸びる last（確定済の辺を格納する次の位置）は、未探索の辺が残っている間は常に top ≦ last であり、探索済の辺が確定済の辺を上書きすることはない。
たどった辺の数 $(top-1)+(M-last)$ が $M$ になる、すなわち top ＝ last＋1 になった時点で、探索済の辺は既に経路の順に path[1]〜path[last] に並んでいる。以降の遡りでは、top を1減らすと top と last が同じ位置になるので、path[last] ← path[top] は同じ要素を同じ位置に書き直すだけの無駄な繰返しになる。したがって繰返し条件は top ≦ last となる（top ＝ last のときは未探索の辺がまだ1本残っている）。境界値（top と last が等しい場合）を含めることが重要である。
よって、条件は topがlast以下 （または top <= last）となる。

高得点のポイント

• 配列を共有した場合に、前方からのポインタ top と後方からのポインタ last がどの時点で探索完了（交差）となるかを理解していること。
• top と last が等しい場合を含む境界値（top <= last または top が last 以下）まで正確に記述できていること。