基本情報技術者試験の公開問題を解こう！（令和６年度・科目B）（3）「グラフを表現する隣接行列を二次元配列で表現」

基本情報技術者試験の令和6年度の公開問題（科目B）を解いてみよう。

この問題は、無向グラフの辺のリストを隣接行列に変換する関数に関するものである。

 問題の概要

• グラフの表現
  • グラフは無向グラフ。
  • 各辺は2つの頂点番号を持つ配列（例：{1, 3}）。
  • 全体のグラフは、こうした辺の配列の配列で表される。
• 隣接行列とは？
  • 頂点数 × 頂点数 の正方行列。
  • 頂点 i と j の間に辺があれば adjMatrix[i][j] = 1。
  • 無向グラフなので adjMatrix[i][j] = adjMatrix[j][i]。
  • 対角成分（adjMatrix[i][i]）は常に 0。

プログラムの目的

関数 edgesToMatrix は、辺の配列 edgeList と頂点数 nodeNum を受け取り、隣接行列 adjMatrix を作成する。

for (i を 1 から edgeListの要素数 まで 1 ずつ増やす)

  u ← edgeList[i][1]

  v ← edgeList[i][2]
  □
endfor

ここで、u と v は辺の両端の頂点番号である。無向グラフなので、adjMatrix[u][v] と adjMatrix[v][u] の両方を 1 にする必要がある。

選択肢を検討していこう。

• ア：adjMatrix[u, u] ← 1 ・・・ 自己ループを意味する。誤り。
• イ：adjMatrix[u, u] ← 1 と adjMatrix[v, v] ← 1 ・・・両方自己ループ。誤り。
• ウ：adjMatrix[u, v] ← 1 ・・・ 片方向のみ。無向グラフには不十分。
• エ：adjMatrix[u, v] ← 1 と adjMatrix[v, u] ← 1 ・・・ ✅ 正解！
• オ：adjMatrix[v, u] ← 1 ・・・ 片方向のみ。誤り。
• カ：adjMatrix[v, v] ← 1・・・ 自己ループ。誤り。

したがって、正解は「エ」である。
adjMatrix[u, v] ← 1
adjMatrix[v, u] ← 1

これにより、無向グラフの隣接行列が正しく構築される。