基本情報技術者試験過去問 令和6年度（2024年）科目B問3
次のプログラム中の に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は1から始まる。
図1に示すグラフの頂点には，1から順に整数で番号が付けられている。グラフは無向グラフであり，各頂点間には高々一つの辺がある。一つの辺は両端の頂点の番号を要素にもつ要素数2の整数型の配列で表現できる。例えば，{1，3}は頂点1と頂点3を端点とする辺を表す。グラフ全体は，グラフに含まれる辺を表す要素数2の配列を全て格納した配列（以下，辺の配列という）で表現できる。辺の配列の要素数はグラフの辺の個数と等しい。図1のグラフは整数型配列の配列{{1, 3}, {1, 4}, {3, 4}, {2, 4}, {4, 5}}と表現できる。
関数edgesToMatrixは，辺の配列を隣接行列に変換する。隣接行列とは，グラフに含まれる頂点の個数と等しい行数及び列数の正方行列で，i行j列の成分は頂点iと頂点jを結ぶ辺があるときに1となり，それ以外は0となる。行列の対角成分は全て0で，無向グラフの場合は対称行列になる。図1のグラフを表現する隣接行列を図2に示す。
関数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, 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
選択肢
- ア
- イ
- ウ
- エ
- オ
- カ
正解と解き方・学習ポイント（AI解説）
無向グラフの隣接行列は、対角成分が0で、行列が対称になります。したがって、辺(u, v)を読み取ったら、隣接行列の(u, v)だけでなく(v, u)も1に更新する必要があります。
Point
この問題は、辺の配列で与えられた無向グラフを隣接行列に変換する際に、無向グラフでは隣接行列を対称にするため2か所を更新する点を理解しているかを問うています。
解くために必要な知識
この問題を解くには、無向グラフと隣接行列の性質を理解している必要があります。
用語の整理
| 用語名 | 意味 |
|---|---|
| 無向グラフ | 辺に向きがないグラフです。頂点uと頂点vが辺で結ばれていれば、uとvは相互に隣接しているとして扱います。 |
| 辺の配列 | 各辺を{u, v}のような要素数2の配列で表し、それらをまとめた配列です。 |
| 隣接行列 | 頂点数nodeNumのnodeNum行nodeNum列の行列です。頂点iと頂点jを結ぶ辺があるとき成分(i, j)が1、ないとき0です。 |
| 対角成分 | (1,1),(2,2),...,(nodeNum,nodeNum)の成分です。この問題では全て0です。 |
| 対称行列 | 成分(i, j)と成分(j, i)が等しい行列です。無向グラフの隣接行列はこの性質を持ちます。 |
無向グラフの隣接行列で行う代入
辺が(u, v)のとき、隣接行列には次の2つを反映します。
-
adjMatrix[u, v] ← 1
-
adjMatrix[v, u] ← 1
図1の例での確認
辺の配列が{{1, 3}, {1, 4}, {3, 4}, {2, 4}, {4, 5}}のとき、例えば{1, 3}は次を意味します。
-
adjMatrix[1, 3] = 1
-
adjMatrix[3, 1] = 1
これを全ての辺について行うと、図2のように対称な隣接行列になります。
問題の解法手順
問題のポイントは、グラフが無向グラフであり、隣接行列が対称になることです。
解く手順
1. 隣接行列の定義を確認します
隣接行列は、頂点iと頂点jを結ぶ辺があるときに成分(i, j)が1になり、それ以外は0になります。
2. 無向グラフの性質を適用します
無向グラフでは、頂点uと頂点vがつながっていることは、
-
uからvがつながっている
-
vからuもつながっている
の両方を意味します。
3. プログラムの空欄に必要な代入を決めます
ループ内でuとvを取り出したあと、隣接行列には次の2つを反映する必要があります。
-
adjMatrix[u, v] ← 1
-
adjMatrix[v, u] ← 1
この2行を行うのは「エ」だけです。
選択肢ごとの解説
- ア：不正解
adjMatrix[u, u]のみを1にしており、uとvを結ぶ辺を表現できません。また、対角成分は0である必要があるため不適切です。よって誤りです。
- イ：不正解
adjMatrix[u, u]とadjMatrix[v, v]を1にしていますが、これは自己ループを表す設定です。この問題では対角成分は0であり、またuとvの接続(adjMatrix[u, v])を表現できないため不適切です。よって誤りです。
- ウ：不正解
adjMatrix[u, v]だけを1にしています。無向グラフではadjMatrix[v, u]も1にして対称にする必要があります。よって誤りです。
- エ：正解
adjMatrix[u, v]とadjMatrix[v, u]の両方を1にしています。無向グラフの隣接行列は対称行列になるため、この処理が必要です。よって正解です。
- オ：不正解
adjMatrix[v, u]だけを1にしています。「ウ」と同様に片側しか設定しておらず、無向グラフの隣接行列として必要な対称性を満たしません。よって誤りです。
- カ：不正解
adjMatrix[v, v]のみを1にしており、uとvを結ぶ辺を表現できません。また、対角成分は0である必要があるため不適切です。よって誤りです。
まとめ
無向グラフの隣接行列は、対角成分が0で、行列が対称になります。したがって、辺(u, v)を読み取ったら、隣接行列の(u, v)だけでなく(v, u)も1に更新する必要があります。
adjMatrix[u, u]のみを1にしており、uとvを結ぶ辺を表現できません。また、対角成分は0である必要があるため不適切です。よって誤りです。
adjMatrix[u, u]とadjMatrix[v, v]を1にしていますが、これは自己ループを表す設定です。この問題では対角成分は0であり、またuとvの接続(adjMatrix[u, v])を表現できないため不適切です。よって誤りです。
adjMatrix[u, v]だけを1にしています。無向グラフではadjMatrix[v, u]も1にして対称にする必要があります。よって誤りです。
adjMatrix[u, v]とadjMatrix[v, u]の両方を1にしています。無向グラフの隣接行列は対称行列になるため、この処理が必要です。よって正解です。
adjMatrix[v, u]だけを1にしています。「ウ」と同様に片側しか設定しておらず、無向グラフの隣接行列として必要な対称性を満たしません。よって誤りです。
adjMatrix[v, v]のみを1にしており、uとvを結ぶ辺を表現できません。また、対角成分は0である必要があるため不適切です。よって誤りです。