2021年 秋期 応用情報技術者試験 問3

一筆書きに関する次の記述を読んで、設問1〜4に答えよ。

グラフは、有限個の点の集合と、その中の2点を結ぶ辺の集合から成る数理モデルである。グラフの点と点の間をつなぐ辺のことを経路という。本問では、任意の2点間で、辺をたどることで互いに行き来することができる経路が存在する（以下、強連結という）有向グラフを扱う。強連結な有向グラフの例を図1に示す。辺は始点と終点の組で定義する。各辺には1から始まる番号が付けられている。

【一筆書き】

本問では、グラフの全ての辺を1回だけ通り、出発点から出て出発点に戻る閉じた経路をもつグラフを、一筆書きができるグラフとする。

【一筆書きの経路の求め方】

一筆書きの経路を求めるためには、出発点から辺の向きに従って辺を順番にたどり、出発点に戻る経路を見つける探索を行う。たどった経路（以下、探索済の経路という）について、グラフ全体で通過していない辺（以下、未探索の辺という）がない場合は、この経路が一筆書きの経路となる。未探索の辺が残っている場合は、探索済の経路を、未探索の辺が接続する点まで遡り、その点を出発点として、同じ点に戻る経路を見つけて、遡る前までの経路に連結することを繰り返す。

各点を始点とする辺を接続辺という。グラフの各点に対して接続辺の集合が決まり、辺の番号が一番小さい接続辺を最初の接続辺という。同じ始点をもつ接続辺の集合で、辺の番号を小さいものから順番に並べたとき、辺の番号が次に大きい接続辺を次の接続辺ということにする。

図1のグラフの各点の接続辺の集合を表1に示す。図1において、点bの最初の接続辺は辺2である。辺2の次の接続辺は辺5となる。辺5の次の接続辺はない。

一筆書きの経路の探索において、一つの点に複数の接続辺がある場合には、最初の接続辺から順にたどることにする。

図1のグラフで点aを出発点とした一筆書きの経路の求め方を図2に示す。経路を構成する辺とその順番が、これ以上変わらない場合、確定済の経路という。

図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→辺8→辺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に示す。

edgefirstによって点2の最初の接続辺が辺2であることが分かり、点2から最初にたどる接続辺は辺2となる。edgenextによって、辺2の次の接続辺が辺5であることが分かるので、点2から次にたどる接続辺は辺5となる。辺5の次の接続辺はないので、点2からたどる接続辺はこれ以上ないことが分かる。

プログラム中で使用する定数と配列を表2に、作成した関数directedEのプログラムを図4に示す。

全ての配列の添字は1から始まる。

function directedE()
    for ( iを1からNまで1ずつ増やす ) // 各点での未探索の辺の番号を初期化
        current[i] ← edgefirst[i]
    endfor
    top ← 1         // 探索済の経路の辺の格納位置を初期化
    last ← M        // 確定済の経路の辺の格納位置を初期化
    x ← 1           // 出発点は点1
    while ( ①lastが1以上 )
        if ( current[x]が ア でない )
            temp ← current[x]           // 点xからたどる接続辺はtemp
            searched[top] ← temp        // 接続辺tempを探索済の経路に登録
            current[x] ← イ    // 点xから次にたどる未探索の辺を格納
            x ← end[temp]               // 接続辺tempの終点を点xにする
            top ← top + 1
        else
            top ← ウ         // 探索済の辺を遡る
            temp ← searched[top]        // 遡った辺はtemp
            path[last] ← temp           // 辺tempを確定済にする
            x ← エ           
            last ← last − 1
        endif
    endwhile
endfunction