過去問解きまくり研究所

令和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, 2, 3, 4, 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のグラフを表現する隣接行列:

( 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
答えと解説を見る

✓ これが正解エadjMatrix[u, v] ← 1 ／ adjMatrix[v, u] ← 1

解説

無向グラフなので、u行v列とv行u列の両方を1にします。

図1のグラフは無向グラフで、辺には向きがありません。頂点1と頂点3を結ぶ辺は、1から3へのつながりでもあり、3から1へのつながりでもあります。問題文にも、隣接行列は対角成分が全て0で、無向グラフの場合は対称行列になると書かれています。軸になるのは、辺を一つ読んだときに行列のどこを1にすれば、この二つの性質を満たせるかです。

プログラムは辺の配列を先頭から一つずつ取り出し、両端の番号をuとvに入れます。空欄で adjMatrix[u, v] ← 1 と adjMatrix[v, u] ← 1 の二つを実行すると、最初の辺{1, 3}で1行3列と3行1列が1になります。続けて{1, 4}、{3, 4}、{2, 4}、{4, 5}を処理すると、1行目は3列と4列、2行目は4列、3行目は1列と4列、4行目は1・2・3・5列、5行目は4列が1になり、図2の行列と全ての成分が一致します。

片方の向きだけを書くと、行列は対称になりません。uやvの対角の位置を1にすると、辺のつながりを記録できないうえ、対角成分は0という決まりにも反します。だから二つの代入をそろえた形が正解です。

見分け方は、無向グラフの隣接行列は対称行列なので、1を書くときは行と列を入れ替えた位置にも書く、と押さえることです。

ほかの選択肢はなぜ違うのか

出典：令和6年度 基本情報技術者試験 科目B 問3

この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）