うごく基本情報

令和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 手)。「真・偽」は、その行の条件の判定です。

手実行した行変わった値
11行目○整数型の二次元配列: edgesToMatrix(整数型配列の配列: edgeList,edgeList = {{1, 3}, {1, 4}, {3, 4}, {2, 4}, {4, 5}}
nodeNum = 5
23行目整数型の二次元配列: 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}}
34行目整数型: i, u, v
45行目for (i を 1 から edgeListの要素数 まで 1 ずつ増やす)真
i = 1
56行目u ← edgeList[i][1]u = 1
67行目v ← edgeList[i][2]v = 3
78行目adjMatrix[u, v] ← 1adjMatrix = {{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}}
89行目adjMatrix[v, u] ← 1adjMatrix = {{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}}
95行目for (i を 1 から edgeListの要素数 まで 1 ずつ増やす)真
i = 2
106行目u ← edgeList[i][1]
117行目v ← edgeList[i][2]v = 4
128行目adjMatrix[u, v] ← 1adjMatrix = {{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}}
139行目adjMatrix[v, u] ← 1adjMatrix = {{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}}
145行目for (i を 1 から edgeListの要素数 まで 1 ずつ増やす)真
i = 3
156行目u ← edgeList[i][1]u = 3
167行目v ← edgeList[i][2]
178行目adjMatrix[u, v] ← 1adjMatrix = {{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}}
189行目adjMatrix[v, u] ← 1adjMatrix = {{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}}
195行目for (i を 1 から edgeListの要素数 まで 1 ずつ増やす)真
i = 4
206行目u ← edgeList[i][1]u = 2
217行目v ← edgeList[i][2]
228行目adjMatrix[u, v] ← 1adjMatrix = {{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}}
239行目adjMatrix[v, u] ← 1adjMatrix = {{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}}
245行目for (i を 1 から edgeListの要素数 まで 1 ずつ増やす)真
i = 5
256行目u ← edgeList[i][1]u = 4
267行目v ← edgeList[i][2]v = 5
278行目adjMatrix[u, v] ← 1adjMatrix = {{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}}
289行目adjMatrix[v, u] ← 1adjMatrix = {{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}}
295行目for (i を 1 から edgeListの要素数 まで 1 ずつ増やす)偽
i = 6
3011行目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}}

サイトで、1行ずつ予想しながら動かす →