問題プレビューID: 58e42ff5基本情報技術者試験 2024年(令和6年度)公開問題 科目B

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

次のプログラム中の [  ] に入れる正しい答えを,解答群の中から選べ。ここで,配列の要素番号は 1 から始まる。

図 1 に示すグラフの頂点には,1 から順に整数で番号が付けられている。グラフは無向グラフであり,各頂点間には高々一つの辺がある。一つの辺は両端の頂点の番号を要素にもつ要素数 2 の整数型の配列で表現できる。例えば,{1, 3} は頂点 1 と頂点 3 を端点とする辺を表す。グラフ全体は,グラフに含まれる辺を表す要素数 2 の配列を全て格納した配列(以下,辺の配列という)で表現できる。辺の配列の要素数はグラフの辺の個数と等しい。図 1 のグラフは整数型配列の配列 {{1, 3}, {1, 4}, {3, 4}, {2, 4}, {4, 5}} と表現できる。

図 1 グラフの例

関数 edgesToMatrix は,辺の配列を隣接行列に変換する。隣接行列とは,グラフに含まれる頂点の個数と等しい行数及び列数の正方行列で,i 行 j 列の成分は頂点 i と頂点 j を結ぶ辺があるときに 1 となり,それ以外は 0 となる。行列の対角成分は全て 0 で,無向グラフの場合は対称行列になる。図 1 のグラフを表現する隣接行列を図 2 に示す。

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
図 2 図 1 のグラフを表現する隣接行列

関数 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

解答群

解説

正解は「エ」です。 無向グラフにおける頂点間の接続関係(辺)を隣接行列で表現する場合、i 行 j 列の成分と j 行 i 列の成分が等しくなる「対称行列」になります。

  • 辺の配列 edgeList から取り出した辺の両端の頂点を u と v とするとき、隣接行列 adjMatrix の u 行 v 列 (adjMatrix[u, v]) を 1 に設定するだけでなく、その対称位置である v 行 u 列 (adjMatrix[v, u]) も 1 に設定する必要があります。
  • したがって、空欄には adjMatrix[u, v] ← 1 と adjMatrix[v, u] ← 1 を両方行う「エ」が適切です。

関連問題

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