はじめに

基本情報技術者試験（令和6年公開問題）の科目Bでは、無向グラフの隣接行列を求めるプログラムに関する問題が出題された。
この問題、一見すると単なるプログラムの穴埋め問題に見えるが、実は無向グラフの特性を正しく理解できているかを試す良問だ。

今回は、令和6年公開問題の科目Bに出題された問3「無向グラフを隣接行列に変換するプログラム」について考えてみよう。

問題の概要

問題では、無向グラフを隣接行列に変換するプログラムが与えられ、そこに適切な処理を補完する必要がある。
まず、例として示されたグラフを確認しよう。

1 - 3
| |
4 - 2
|
5

このグラフは、「辺のリスト」 で表現できる。

{{1, 3}, {1, 4}, {3, 4}, {2, 4}, {4, 5}}

このデータを基に、隣接行列（adjacency matrix）を作成するのが本問題の目的である。

隣接行列とは？

隣接行列とは、頂点数 × 頂点数 の正方行列であり、
– i行j列の要素が1 のとき、頂点 i と頂点 j の間に辺が存在することを示す。
– 無向グラフ の場合は 対称行列 となる（A[i][j] = A[j][i]）。
– 自己ループ（同じ頂点への辺）は存在しないため、対角成分はすべて0。

問題文のグラフを隣接行列にすると、以下のようになる。

この特性を意識して、プログラムの穴埋めを考えていこう。

プログラムの穴埋め問題を考察

与えられたプログラムを確認する。

整数型の二次元配列: 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

ここで、u と v は、それぞれ辺の両端の頂点番号を表す。
適切な処理を入れて、隣接行列 adjMatrix を構築する必要がある。

選択肢の分析

選択肢を詳しく見ていこう。

したがって、正解は「エ」 である。

Python での実装

この問題を Python で実装すると、以下のようになる。

def edges_to_matrix(edge_list, node_num):
# 隣接行列を 0 で初期化
adj_matrix = [[0] * node_num for _ in range(node_num)]

# 辺の情報を隣接行列に反映
for u, v in edge_list:
adj_matrix[u-1][v-1] = 1
adj_matrix[v-1][u-1] = 1 # 無向グラフの対称性を保証

return adj_matrix

# 辺のリスト
edges = [(1, 3), (1, 4), (3, 4), (2, 4), (4, 5)]
node_count = 5

# 隣接行列の生成
adjacency_matrix = edges_to_matrix(edges, node_count)

# 出力
for row in adjacency_matrix:
print(row)

このコードを実行すると、問題文の隣接行列と同じ結果が得られるはずだ。

[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]

まとめ

1. 無向グラフの隣接行列 とは、頂点間の接続関係を示す対称行列である。
2. 対称行列 の特性を守るために、 adjMatrix[u, v] だけでなく adjMatrix[v, u] も 1 にする必要がある。
3. プログラムの穴埋めでは「エ」 (adjMatrix[u, v] ← 1; adjMatrix[v, u] ← 1) が正解 だった。
4. Python で実装 すれば、実際の挙動を確認できる。

「無向グラフの隣接行列」と聞くと、数学的で少し難しく感じるかもしれない。
しかし、考え方自体はシンプルで、「対称性を意識する」ことがポイントとなる。試験本番でも、この考え方をしっかり押さえておこう。