問題
関数 edgesToMatrix は、無向グラフの辺の配列を隣接行列に変換する。辺は両端の頂点番号を要素にもつ要素数 2 の配列で表す。隣接行列の i 行 j 列は頂点 i と頂点 j を結ぶ辺があれば 1、なければ 0 となり、無向グラフでは対称行列になる。配列の要素番号は 1 から始まる。図のグラフ・隣接行列・プログラムを踏まえ、プログラム中の空欄に入れる正しい答えを、解答群の中から選べ。
選択肢
- 1adjMatrix[u, u] ← 1
- 2adjMatrix[u, u] ← 1 / adjMatrix[v, v] ← 1
- 3adjMatrix[u, v] ← 1
- 4adjMatrix[u, v] ← 1 / adjMatrix[v, u] ← 1
- 5adjMatrix[v, u] ← 1
- 6adjMatrix[v, v] ← 1
正解
4. adjMatrix[u, v] ← 1 / adjMatrix[v, u] ← 1
詳しい解説を見る解説を閉じる
解説
ループ内で u には辺の一方の端点 edgeList[i][1]、v には他方の端点 edgeList[i][2] が入る。頂点 u と頂点 v の間に辺があるのだから、隣接行列の u 行 v 列を 1 にする必要がある。さらに無向グラフでは辺に向きがなく、隣接行列は対称行列になるため、v 行 u 列も 1 にしなければならない。したがって adjMatrix[u, v] ← 1 と adjMatrix[v, u] ← 1 の両方を行うエが正解。ウや オ のように片方だけだと対称性が崩れ、図 2 のような対称な隣接行列にならない。ア・イ・カ は対角成分（自分自身との辺）を 1 にしており、辺の表現として誤り。よってエが正解。（出典: 令和6年度 基本情報技術者試験 科目B 問3）
一問一答
科目A 180問+科目B 60問