令和6年度 公開問題 科目B 問3
次のプログラム中の[ ]に入れる正しい答えを,解答群の中から選べ。ここで,配列の要素番号は 1 から始まる。
図 1 に示すグラフの頂点には,1 から順に整数で番号が付けられている。グラフは無向グラフであり,各頂点間には高々一つの辺がある。一つの辺は両端の頂点の番号を要素にもつ要素数 2 の整数型の配列で表現できる。例えば,{1,3} は頂点 1 と頂点 3 を端点とする辺を表す。グラフ全体は,グラフに含まれる辺を表す要素数 2 の配列を全て格納した配列(以下,辺の配列という)で表現できる。辺の配列の要素数はグラフの辺の個数と等しい。図 1 のグラフは整数型配列の配列{{1, 3}, {1, 4}, {3,4}, {2, 4}, {4, 5}}と表現できる。
13245
図 1 グラフの例関数 edgesToMatrix は,辺の配列を隣接行列に変換する。隣接行列とは,グラフに含まれる頂点の個数と等しい行数及び列数の正方行列で,i 行 j 列の成分は頂点 i と頂点 j を結ぶ辺があるときに 1 となり,それ以外は 0 となる。行列の対角成分は全て0 で,無向グラフの場合は対称行列になる。図 1 のグラフを表現する隣接行列を図 2に示す。
0[ ]0[ ]1[ ]1[ ]00[ ]0[ ]0[ ]1[ ]01[ ]0[ ]0[ ]1[ ]01[ ]1[ ]1[ ]0[ ]10[ ]0[ ]0[ ]1[ ]0
図 2 図 1 のグラフを表現する隣接行列関数 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]
[ a ]
endfor
return adjMatrix
| a | |
|---|---|
| ア | 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 |
出典:令和6年度 基本情報技術者試験 科目B 公開問題 問3
正解と解説を見る
正解:エ
ポイント:無向グラフの隣接行列は対称。辺 u-v があれば [u, v] と [v, u] の両方を 1 にする。
辺のリスト(例:{1, 3} は頂点1と頂点3を結ぶ辺)から、隣接行列を作る関数です。隣接行列では、頂点 u と頂点 v の間に辺があれば、u 行 v 列を 1 にします。
この問題のグラフは無向グラフ(辺に向きがない)です。辺 {1, 3} は「1 から 3 へ」でもあり「3 から 1 へ」でもあるので、adjMatrix[u, v] と adjMatrix[v, u] の両方を 1 にします(エ)。こうしてできる行列は、左上から右下への対角線について対称になります。
ウ:[u, v] だけだと、片方向の辺(有向グラフ)になってしまいます。
オ:[v, u] だけも同じく片方向です。
ア・イ・カ:[u, u] や [v, v] は対角線の位置で、「自分自身への辺」を表します。辺の情報にはなりません。
解説と下の表はこのサイトが作成したものです(表は、正解の選択肢を入れたプログラムを実際に実行した結果です)。
正解のプログラムを動かしてみる
edgesToMatrix({{1, 3}, {1, 4}, {3, 4}, {2, 4}, {4, 5}}, 5) を呼び出したときに、1行ずつ何が起きるかの表です(全部で 30 手)。「真・偽」は、その行の条件の判定です。
| 手 | 実行した行 | 変わった値 |
|---|---|---|
| 1 | 1行目○整数型の二次元配列: edgesToMatrix(整数型配列の配列: edgeList, | edgeList = {{1, 3}, {1, 4}, {3, 4}, {2, 4}, {4, 5}} nodeNum = 5 |
| 2 | 3行目整数型の二次元配列: adjMatrix ← {nodeNum行nodeNum列の 0} | adjMatrix = {{0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}} |
| 3 | 4行目整数型: i, u, v | |
| 4 | 5行目for (i を 1 から edgeListの要素数 まで 1 ずつ増やす) | 真 i = 1 |
| 5 | 6行目u ← edgeList[i][1] | u = 1 |
| 6 | 7行目v ← edgeList[i][2] | v = 3 |
| 7 | 8行目adjMatrix[u, v] ← 1 | adjMatrix = {{0, 0, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}} |
| 8 | 9行目adjMatrix[v, u] ← 1 | adjMatrix = {{0, 0, 1, 0, 0}, {0, 0, 0, 0, 0}, {1, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}} |
| 9 | 5行目for (i を 1 から edgeListの要素数 まで 1 ずつ増やす) | 真 i = 2 |
| 10 | 6行目u ← edgeList[i][1] | |
| 11 | 7行目v ← edgeList[i][2] | v = 4 |
| 12 | 8行目adjMatrix[u, v] ← 1 | adjMatrix = {{0, 0, 1, 1, 0}, {0, 0, 0, 0, 0}, {1, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}} |
| 13 | 9行目adjMatrix[v, u] ← 1 | adjMatrix = {{0, 0, 1, 1, 0}, {0, 0, 0, 0, 0}, {1, 0, 0, 0, 0}, {1, 0, 0, 0, 0}, {0, 0, 0, 0, 0}} |
| 14 | 5行目for (i を 1 から edgeListの要素数 まで 1 ずつ増やす) | 真 i = 3 |
| 15 | 6行目u ← edgeList[i][1] | u = 3 |
| 16 | 7行目v ← edgeList[i][2] | |
| 17 | 8行目adjMatrix[u, v] ← 1 | adjMatrix = {{0, 0, 1, 1, 0}, {0, 0, 0, 0, 0}, {1, 0, 0, 1, 0}, {1, 0, 0, 0, 0}, {0, 0, 0, 0, 0}} |
| 18 | 9行目adjMatrix[v, u] ← 1 | adjMatrix = {{0, 0, 1, 1, 0}, {0, 0, 0, 0, 0}, {1, 0, 0, 1, 0}, {1, 0, 1, 0, 0}, {0, 0, 0, 0, 0}} |
| 19 | 5行目for (i を 1 から edgeListの要素数 まで 1 ずつ増やす) | 真 i = 4 |
| 20 | 6行目u ← edgeList[i][1] | u = 2 |
| 21 | 7行目v ← edgeList[i][2] | |
| 22 | 8行目adjMatrix[u, v] ← 1 | adjMatrix = {{0, 0, 1, 1, 0}, {0, 0, 0, 1, 0}, {1, 0, 0, 1, 0}, {1, 0, 1, 0, 0}, {0, 0, 0, 0, 0}} |
| 23 | 9行目adjMatrix[v, u] ← 1 | adjMatrix = {{0, 0, 1, 1, 0}, {0, 0, 0, 1, 0}, {1, 0, 0, 1, 0}, {1, 1, 1, 0, 0}, {0, 0, 0, 0, 0}} |
| 24 | 5行目for (i を 1 から edgeListの要素数 まで 1 ずつ増やす) | 真 i = 5 |
| 25 | 6行目u ← edgeList[i][1] | u = 4 |
| 26 | 7行目v ← edgeList[i][2] | v = 5 |
| 27 | 8行目adjMatrix[u, v] ← 1 | adjMatrix = {{0, 0, 1, 1, 0}, {0, 0, 0, 1, 0}, {1, 0, 0, 1, 0}, {1, 1, 1, 0, 1}, {0, 0, 0, 0, 0}} |
| 28 | 9行目adjMatrix[v, u] ← 1 | adjMatrix = {{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}} |
| 29 | 5行目for (i を 1 から edgeListの要素数 まで 1 ずつ増やす) | 偽 i = 6 |
| 30 | 11行目return adjMatrix |
戻り値:{{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}}