基本情報技術者試験 令和6年度 公開問題 科目B、全6問のうちの問3。
出典：令和6年度 基本情報技術者試験 公開問題 科目B 問3（図 1 のグラフの絵は、問題文の辺の配列に合わせて、辺ごとの両端の頂点の表に書き起こした。図 2 の行列は表に書き起こし、行と列の番号を足した。プログラムは原本の画像を文字に書き起こし、字下げは 1 段を空白 2 つで表した。関数の宣言の 2 行目は、原本どおり引数の位置にそろえた。空欄は［ ］で表した。2 行から成る選択肢 (イとエ) は、2 つの文を「，」で並べて 1 行にした）
次の
図 1 に
| 辺 | 一方の頂点 | もう一方の頂点 |
|---|---|---|
| {1, 3} | 1 | 3 |
| {1, 4} | 1 | 4 |
| {3, 4} | 3 | 4 |
| {2, 4} | 2 | 4 |
| {4, 5} | 4 | 5 |
関数 edgesToMatrix は，
| 行＼列 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 1 | 1 | 0 |
| 2 | 0 | 0 | 0 | 1 | 0 |
| 3 | 1 | 0 | 0 | 1 | 0 |
| 4 | 1 | 1 | 1 | 0 | 1 |
| 5 | 0 | 0 | 0 | 1 | 0 |
関数 edgesToMatrix は，
○整数型の二次元配列: edgesToMatrix(整数型配列の配列: edgeList,整数型: nodeNum)整数型の二次元配列: adjMatrix ← {nodeNum行nodeNum列の 0}整数型: i, u, vfor (i を 1 から edgeListの要素数 まで 1 ずつ増やす)u ← edgeList[i][1]v ← edgeList[i][2]［ ］endforreturn adjMatrix
- アadjMatrix[u, u] ← 1
- イadjMatrix[u, u] ← 1，
adjMatrix[v, v] ← 1 の 2 行 - ウadjMatrix[u, v] ← 1
- エadjMatrix[u, v] ← 1，
adjMatrix[v, u] ← 1 の 2 行 - オadjMatrix[v, u] ← 1
- カadjMatrix[v, v] ← 1
答えと解説を開く
正解はエです。
隣接行列の
ほかの選択肢が違う理由
- ア対角成分の
u 行 u 列を 1 に しています。 隣接行列の 対角成分は 全て 0 で、 辺の 相手の v が 行列に 現れません。 - イ対角成分の
u 行 u 列と v 行 v 列を 1 に しています。 頂点どうしの つながりが 記録されません。 - ウu 行 v 列だけを
1 に しています。 この 例の 辺は どれも u ＜ v なので右上の 半分しか 埋まらず、 たとえば 3 行 1 列が 0 のままで、 図 2 の 対称行列に なりません。 - オv 行 u 列だけを
1 に しています。 この 例では 左下の 半分しか 埋まらず、 たとえば 1 行 3 列が 0 のままです。 - カ対角成分の
v 行 v 列を 1 に しています。 隣接行列の 対角成分は 全て 0 です。
仕組み
グラフの
無向グラフでは