一筆書きに関する次の記述を読んで，設問1〜4に答えよ。
グラフは，有限個の点の集合と，その中の2点を結ぶ辺の集合から成る数理モデルである。グラフの点と点の間をつなぐ辺の列のことを経路という。本問では，任意の2点間で，辺をたどることで互いに行き来することができる経路が存在する（以下，強連結という）有向グラフを扱う。強連結な有向グラフの例を図1に示す。辺は始点と終点の組で定義する。各辺には1から始まる番号が付けられている。
図1 強連結な有向グラフの例
〔一筆書き〕
本問では，グラフの全ての辺を1回だけ通り，出発点から出て出発点に戻る閉じた経路をもつグラフを，一筆書きができるグラフとする。
〔一筆書きの経路の求め方〕
一筆書きの経路を求めるためには，出発点から辺の向きに従って辺を順番にたどり，出発点に戻る経路を見つける探索を行う。たどった経路（以下，探索済の経路という）について，グラフ全体で通過していない辺（以下，未探索の辺という）がない場合は，この経路が一筆書きの経路となる。未探索の辺が残っている場合は，探索済の経路を，未探索の辺が接続する点まで遡り，その点を出発点として，同じ点に戻る経路を見つけて，遡る前までの経路に連結することを繰り返す。
各点を始点とする辺を接続辺という。グラフの各点に対して接続辺の集合が決まり，辺の番号が一番小さい接続辺を最初の接続辺という。同じ始点をもつ接続辺の集合で，辺の番号を小さいものから順番に並べたときに，辺の番号が次に大きい接続辺を次の接続辺ということにする。
図1のグラフの各点の接続辺の集合を表1に示す。図1において，点bの最初の接続辺は辺2である。辺2の次の接続辺は辺5となる。辺5の次の接続辺はない。
| 点 | 接続辺の集合 |
| 点a | 辺1 |
| 点b | 辺2，辺5 |
| 点c | 辺3 |
| 点d | 辺4，辺7 |
| 点e | 辺6 |
| 点f | 辺8 |
一筆書きの経路の探索において，一つの点に複数の接続辺がある場合には，最初の接続辺から順にたどることにする。
図1のグラフで点aを出発点とした一筆書きの経路の求め方を図2に示す。
経路を構成する辺とその順番が，これ以上変わらない場合，確定済の経路という。
図2 図1のグラフで点aを出発点とした一筆書きの経路の求め方
図2を参考にした一筆書きの経路を求める手順を次に示す。
〔一筆書きの経路を求める手順〕
点aから探索する場合は，点aの最初の接続辺である辺1から始め，辺1の終点bの最初の接続辺である辺2をたどり，同様に辺3，辺4をたどる。辺4の終点aからたどれる未探索の辺は存在しないので，これ以上探索が進められない（図2[1]）。
しかし，未探索の辺5，辺6，辺7，辺8が残っているので，未探索の辺が接続する点まで遡る。
終点aから辺4を遡ると，辺4の始点dで未探索の辺7が接続している。遡った経路は途中で未探索の辺が存在しないので，これ以上，辺の順番が変わらず，辺4は，一筆書きの経路の一部として確定済の経路となる（図2[2]）。
点dから同様に辺7→辺8→辺5→辺6と探索できるので，辺3までの経路と連結した新しい探索済の経路ができる（図2[3]）。
辺6の終点dからは，辺6→辺5→78→辺7→辺3→辺2→辺1と出発点の点aまで遡り，これ以上，未探索の辺がないことが分かるので，全ての辺が確定済の経路になる（図2[4]）。
一筆書きの経路は，次の（1）〜（4）の手順で求められる。
（1）一筆書きの経路の出発点を決める。
（2）出発点から，未探索の辺が存在する限り，その辺をたどり，たどった経路を探索済の経路に追加する。
（3）探索済の経路を未探索の辺が接続する点又は一筆書きの経路の出発点まで遡る。遡った経路は，探索済の経路から確定済の経路にする。未探索の辺が接続する点がある場合は，それを新たな出発点として，（2）に戻って新たな経路を見つける。
（4）全ての辺が確定済の経路になった時点で探索が完了して，その確定済の経路が一筆書きの経路になる。
一筆書きの経路を求める関数directedEのプログラムを作成した。
実装に当たって，各点を点n（nは1〜N）と記す。例えば，図1のグラフでは，点aは点1，点bは点2と記す。
グラフの探索のために，あらかじめ，グラフの点に対する最初の接続辺の配列edgefirst及び接続辺に対する次の接続辺の配列edgenextを用意しておく。edgenextにおいて，次の接続辺がない場合は，要素に0を格納する。
図1のグラフの場合の配列edgefirst，edgenextを図3に示す。
図3 図1のグラフの場合の配列edgefirst，edgenext
edgefirstによって点2の最初の接続辺が辺2であることが分かり，点2から最初にたどる接続辺は辺2となる。edgenextによって，辺2の次の接続辺が辺5であることが分かるので，点2から次にたどる接続辺は辺5となる。辺5の次の接続辺はないので，点2からたどる接続辺はこれ以上ないことが分かる。
プログラム中で使用する定数と配列を表2に，作成した関数directedEのプログラムを図4に示す。
全ての配列の添字は1から始まる。
| 名前 | 種類 | 内容 |
| N | 定数 | グラフの点の個数 |
| M | 定数 | グラフの辺の個数start[m] |
| start[m] | 配列 | start[m]には，辺mの始点の番号が格納されている。 |
| end[m] | 配列 | end[m]には，辺mの終点の番号が格納されている。 |
| edgefirst[n] | 配列 | 配列edgefirst[n]には，点nの最初の接続辺の番号が格納されている。 |
| edgenext[m] | 配列 | 配列edgenext[m]には，辺mの次の接続辺の番号が格納されている。次の接続辺がない場合は0が格納されている。 |
| current[n] | 配列 | 配列current[n]には，点nを始点とする未探索の辺の中で最小の番号を格納する。点nを始点とする未探索の辺がない場合は0を格納する。 |
| searched[m] | 配列 | 配列一筆書きの経路を構成する探索済の辺の番号を順番に格納する。（探索済の経路） |
| path[m] | 配列 | 配列一筆書きの経路を構成する確定済の辺の番号を順番に格納する。（確定済の経路） |
図4 関数directedEのプログラム
出典：令和3年度秋期 問3
設問1 図4中の ア 〜 エ に入れる適切な字句を答えよ。
解答・解説
解答例
準備中
解説
設問2 図1のグラフで関数directedEを動作させたとき，while文中のif文は，何回実行されるか，数値で答えよ。
解答・解説
解答例
準備中
解説
設問3 一筆書きができない強連結な有向グラフで関数directedEを動作させたとき，探索はどのようになるかを，解答群の中から選び，記号で答えよ。
解答群
- 探索が完了するが，配列pathに格納された経路は一筆書きの経路にならない。
- 探索が完了せずに終了して，配列pathに格納された経路は一筆書きの経路にならない。
- 探索が無限ループに陥り，探索が終了しない。
解答・解説
解答例
準備中
解説
設問4 図4のプログラムは，配列searchedを配列pathに置き換えることで，使用する領域を減らすことができる。このとき，無駄な繰返しが発生しないように，下線①の繰返し条件を，変数topとlastを用いて変更せよ。。
解答・解説
解答例
準備中
解説
IPA公開情報
出題趣旨
“もの”と“もの”が複雑につながり合っているときに，つながり具合だけに注目して議論するのにグラフは適している。
本問では，一筆書きを題材に，応用範囲が広いグラフを扱うアルゴリズムに関する理解とその実装を問う。
採点講評
問 3 では，一筆書きを題材に，応用範囲が広いグラフを扱うアルゴリズムの理解とその実装について出題し た。全体として正答率は平均的であった。
設問 1 のイは，正答率がやや低かった。配列 edgefirst と配列 edgenext の関係を例示した図 3 も参考にして， 点 x から次にたどる未探索の辺の求め方を理解してほしい。
設問 2 は，正答率が低かった。図 2 及び〔一筆書きの経路を求める手順〕から，グラフの各辺は，一度，探 索済になってから確定済になることに注目して，if 文の実行回数が辺の数の 2 倍になることを理解してほしい。
設問 4 は，正答率が低かった。“top が last より小さい”など，top と last が等しい場合を含まない，誤った解答をした受験者が多かった。プログラム中の分岐や繰返しの条件は，その境界値まで正確に記述できているかどうかを，常に確認するようにしてほしい。
