応用情報技術者 2021年 秋期 午後 問03

解答の論理構成

1. if (currentx が ア でない) の判定
   • 表2に「currentnには、点nを始点とする未探索の辺がない場合は0を格納する。」とあります。
   • よって「未探索の辺があるか」を判定する値は 0 です。
     ⇒ ア ＝ 0
2. currentx ← イ の更新
   • 未探索だった辺 temp を取り出した直後は、その次の接続辺を current にセットする必要があります。
   • 図1の説明には「edgenextによって、辺2の次の接続辺が辺5であることが分かる」とあります。
   • したがって currentx には edgenext[temp] を代入します。
     ⇒ イ ＝ edgenext[temp]
3. backtrack 部分 top ← ウ
   • 探索済スタック searched は top で末尾位置（次に書き込む場所）を示します。
   • 一つ戻るには「1 減算」します。
     ⇒ ウ ＝ top - 1
4. x ← エ の更新
   • 遡った辺 temp の始点へ戻るので、表2の startm を参照します。
   • 具体例として図2[2]では「辺4を遡ると、辺4の始点d…」という処理が行われています。
     ⇒ エ ＝ start[temp]

• ア 0
• イ edgenext[temp]
• ウ top - 1
• エ start[temp]

誤りやすいポイント

• 「currentx==0 は“接続辺が無い”」という定義を見落とし、NULL や負数を入れてしまう。
• top の意味を「現在の格納済み位置」ではなく「最後に格納した位置」と誤解し、top ← top - 1 を忘れる。
• 遡り時に終点 end[temp] を入れてしまい、無限ループに陥る。
• edgenext と edgefirst を取り違えて、次の接続辺の更新が壊れる。

FAQ

解答の論理構成

1. ループ条件の確認
   • プログラムでは last ← M と初期化され、while (①last が 1 以上) で繰り返します。
   • M は【表2】で「グラフの辺の個数」と定義されています。図1のグラフでは「辺1」〜「辺8」が列挙されているので M = 8 です。
2. last が減るタイミング
   • else 句に last ← last − 1 があり、if 句側には last を変更する文がありません。
   • よって last を減らすのは else が実行されたときだけです。
   • ループ終了条件は last < 1 になるまでなので、else はちょうど M 回、すなわち 8 回 実行されます。
3. ループ回数の算出
   • else が 8 回実行されるあいだ、if も含めて毎回判定が行われるため、総ループ回数は
     8（if 側で探索に進む回数） + 8（else 側で遡る回数） = 16 回です。
   • したがって if 文は 16 回評価 され、「何回実行されるか」という設問の答えは 16 になります。

誤りやすいポイント

• top を増減させている行に目を取られ、last だけを減らす場所を見落とす。
• if 側で複数の辺を一気に処理すると思い込み、探索回数と if 評価回数を混同する。
• while を抜けた後にもう一度 if が評価されると誤解し、+1 してしまう。

FAQ

解答の論理構成

1. ループの終了条件を確認
   プログラムでは「while (①last が 1 以上)」と明記されています。さらに、初期化時に「last ← M」とし、else 節に入るたびに「last ← last − 1」で必ず 1 つ減らします。したがって 辺を確定済にするたびに last は 1 減り、last が 0 になれば必ず while ループは終了します。
2. last が 0 になるまでに何回減るか
   if 節では探索済スタックに push するだけで last は減りません。else 節で pop したときだけ減ります。push された総数はちょうどグラフの辺の個数 M、pop される回数も M なので、last は必ず 0 になります。
3. グラフが一筆書き不可でも終了できる理由
   アルゴリズムは【問題文】の「(2) 出発点から、未探索の辺が存在する限り…」「(3) 探索済の経路を未探索の辺が接続する点…」を忠実に模倣していますが、“閉路になる” 条件はコード中に組み込まれていません。入次数＝出次数という Euler 条件を満たさない有向グラフでも、 ・未探索の辺があれば必ず if 節で push
   ・未探索の辺が尽きれば else 節で pop
   を繰り返すだけなのでループ自体は正常終了します。
4. path に格納される経路の性質
   一筆書きが可能になる必要十分条件は各点で「入次数＝出次数」です。しかし設問では「一筆書きができない強連結な有向グラフ」と明言されています。よって 完成した path はすべての辺を含むものの、出発点に戻らない（途中で不整合が起こる）ので一筆書きの経路にはなりません。
5. 解答選択
   以上より「探索が完了」かつ「path は一筆書きにならない」状況なので、解答群の
   ア：探索が完了するが、配列pathに格納された経路は一筆書きの経路にならない。
   が該当します。

誤りやすいポイント

• last の役割を「確定済辺の個数」ではなく「格納位置」と取り違えると、無限ループと勘違いしやすいです。
• Euler 条件を満たさないと探索アルゴリズム自体が停止しないと思い込みがちですが、directedE は「辺数が有限」である限り必ず last を 0 にできます。
• top ← top - 1 の直後に searched[top] を参照するので、「スタックが空になった瞬間に underflow する」と誤解しやすいですが、push 回数＝pop 回数なので underflow にはなりません。

FAQ

解答の論理構成

1. ループ開始時の変数の役割を整理します。問題文には
   • 「top ← 1」「last ← M」
     とあり、top は配列searched（探索済の経路）の「次に格納する位置」、last は配列path（確定済の経路）の「次に格納する位置」を示しています。
2. 探索が進むにつれて
   • 探索済の辺を追加すると top ← top + 1
   • 遡って確定すると last ← last − 1
     が実行され、top はインクリメント、last はデクリメントされます。
3. すべての辺を確定し終える瞬間は「探索済に入れる位置 top が、確定済に入れる位置 last を追い越した」瞬間です。これ以上 while 文を回しても何も処理できません。
4. したがって、下線①の条件
   「while (last が 1 以上)」
   を、処理が残っている状態──すなわち「top が last 以下」のあいだだけ繰り返す条件に置き換えれば、無駄なループは起きません。
5. よって模範解答は
   topがlast以下

誤りやすいポイント

• ①を「top <= M」など配列長と比較してしまう。探索の進行度を示すのは last であって M ではありません。
• top と last が「インデックス」ではなく「要素数」だと誤解する。実際には「次に格納する位置」です。
• 「探索済が空になったら終了」と考えて top == 1 を判定に用いるミス。確定済へ移すたびに探索済の末尾要素は削除されるため、top が 1 でも探索が終わっているとは限りません。

FAQ