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

解答の論理構成

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

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

誤りやすいポイント

• 「current[x]==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