問題プレビューID: 5852b937応用情報技術者試験 2021年(令和3年度)秋期 午後

問 3
応用情報技術者試験 2021年(令和3年度)秋期 午後

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

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

図1 強連結な有向グラフの例

辺1=(点a,点b) 辺2=(点b,点c) 辺3=(点c,点d) 辺4=(点d,点a) 辺5=(点b,点e) 辺6=(点e,点d) 辺7=(点d,点f) 辺8=(点f,点b)

凡例 辺=(辺の始点,辺の終点)

〔一筆書き〕

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

〔一筆書きの経路の求め方〕

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

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

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

表1 図1のグラフの各点の接続辺の集合

点接続辺の集合
点a辺1
点b辺2,辺5
点c辺3
点d辺4,辺7
点e辺6
点f辺8

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

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

図2 図1のグラフで点aを出発点とした一筆書きの経路の求め方

図2は,[1]~[4]の四つの段階から成る。各段階は点a,点b(右上),点d(左下),点c(右下)を頂点とする方形の図であり,辺1(上辺,a→b),辺2(右辺,b→c),辺3(下辺,c→d),辺4(左辺,d→a),辺5(b→e),辺6(e→d),辺7(d→f),辺8(f→b)を示す。実線は探索済,破線は未探索,太線は確定済を表す。[1]では辺1~辺4が探索済(実線),辺5~辺8が未探索(破線)である。[2]では辺4が確定済(太線)となる。[3]では点dから辺7→辺8→辺5→辺6と探索し,辺3までの経路と連結した新しい探索済の経路ができる。[4]では全ての辺が確定済の経路(太線)になる。

凡例 ――:探索済 - - - -:未探索 ━━:確定済

注記1 点や辺の番号を一部省略している。

注記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に示す。

図3 図1のグラフの場合の配列edgefirst,edgenext

点123456
edgefirst123468
辺12345678
edgenext05070000

注記 edgefirstにはグラフの点に対する最初の接続辺の番号を格納している。edgenextには接続辺の次の接続辺の番号を格納している。

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

プログラム中で使用する定数と配列を表2に,作成した関数directedEのプログラムを図4に示す。全ての配列の添字は1から始まる。

表2 使用する定数と配列

名称種類内容
N定数グラフの点の個数
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のプログラム

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

設問1

図4中の[ア]~[エ]に入れる適切な字句を答えよ。

設問2

図1のグラフで関数directedEを動作させたとき,while文中のif文は,何回実行されるか,数値で答えよ。

設問3

一筆書きができない強連結な有向グラフで関数directedEを動作させたとき,探索はどのようになるかを,解答群の中から選び,記号で答えよ。

解答群

ア 探索が完了するが,配列pathに格納された経路は一筆書きの経路にならない。

イ 探索が完了せずに終了して,配列pathに格納された経路は一筆書きの経路にならない。

ウ 探索が無限ループに陥り,探索が終了しない。

設問4

図4のプログラムは,配列searchedを配列pathに置き換えることで,使用する領域を減らすことができる。このとき,無駄な繰返しが発生しないように,下線①の繰返し条件を,変数topとlastを用いて変更せよ。

模範解答

設問1 ア 0,イ edgenext[temp],ウ top - 1,エ start[temp]

設問2 16

設問3 ア

設問4 top が last 以下

解説

本問では,一筆書きを題材に,応用範囲が広いグラフを扱うアルゴリズムに関する理解とその実装を問う。

設問1のアは,未探索の辺がないことの判定であり,current[x]が0でないことである。イは,点xから次にたどる未探索の辺であり,edgenext[temp]である。ウは,探索済の辺を遡る処理であり,top - 1である。エは,遡った辺の始点に戻る処理であり,start[temp]である。

設問2では,図1のグラフ(辺8本)で関数directedEを動作させたとき,while文中のif文は16回実行される。

設問3では,一筆書きができない強連結な有向グラフでも探索は完了するが,配列pathに格納された経路は一筆書きの経路にならない(ア)。

設問4では,配列searchedを配列pathに置き換えて領域を減らすとき,繰返し条件をtop が last 以下に変更する。

関連問題

本文が同じ・似ている問題を表示しています