令和6年度 基本情報技術者試験 科目B 公開問題 問3

次のプログラム中の　に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は 1 から始まる。 図 1 に示すグラフの頂点には，1 から順に整数で番号が付けられている。グラフは無向グラフであり，各頂点間には高々一つの辺がある。一つの辺は両端の頂点の番号を要素にもつ要素数 2 の整数型の配列で表現できる。例えば，{1，3} は頂点 1 と頂点 3 を端点とする辺を表す。グラフ全体は，グラフに含まれる辺を表す要素数 2 の配列を全て格納した配列（以下，辺の配列という）で表現できる。辺の配列の要素数はグラフの辺の個数と等しい。図 1 のグラフは整数型配列の配列{{1, 3}, {1, 4}, {3, 4}, {2, 4}, {4, 5}}と表現できる。 〔図〕図1　グラフの例：頂点 1～5 を丸で示した無向グラフ。辺は 1―3，1―4，3―4，2―4，4―5（頂点 3 が上，1 が左，4 が中央，2 が左下，5 が右下に配置）。 関数 edgesToMatrix は，辺の配列を隣接行列に変換する。隣接行列とは，グラフに含まれる頂点の個数と等しい行数及び列数の正方行列で，i 行 j 列の成分は頂点 i と頂点 j を結ぶ辺があるときに 1 となり，それ以外は 0 となる。行列の対角成分は全て 0 で，無向グラフの場合は対称行列になる。図 1 のグラフを表現する隣接行列を図 2 に示す。 〔図〕図2　図 1 のグラフを表現する隣接行列（5 行 5 列，丸括弧で囲まれた行列）： 0 0 1 1 0 0 0 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 0 関数 edgesToMatrix は，引数 edgeList で辺の配列を，引数 nodeNum でグラフの頂点の個数をそれぞれ受け取り，隣接行列を表す整数型の二次元配列を返す。 〔プログラム〕

○整数型の二次元配列: edgesToMatrix(整数型配列の配列: edgeList,
                                    整数型: nodeNum)
  整数型の二次元配列: adjMatrix ← {nodeNum行nodeNum列の 0}
  整数型: i, u, v
  for (i を 1 から edgeListの要素数 まで 1 ずつ増やす)
    u ← edgeList[i][1]
    v ← edgeList[i][2]
    　
  endfor
  return adjMatrix