基本情報技術者試験 | 令和6年度(科目B) [問3]　過去問解説

問題

問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でグラフの頂点の個数をそれぞれ受け取り、隣接行列を表す整数型の二次元配列を返す。

• ア：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]

スポンサーリンク

正解

正解は「エ」です。

問題概要

グラフの説明

この問題は「グラフ」という構造を、プログラムでどう表現し、どう変換するかを問う問題です。
グラフといっても、図形ではなく、**点（頂点）と線（辺）**で構成される「情報のつながり」を示すものです。

図1のグラフとは：

図1では、以下のように頂点（ノード）1～5があり、線（辺）でつながれています。

• 頂点1と3がつながっている → {1, 3}
• 頂点1と4がつながっている → {1, 4}
• 頂点3と4がつながっている → {3, 4}
• 頂点2と4がつながっている → {2, 4}
• 頂点4と5がつながっている → {4, 5}

このように、グラフ全体は「辺のリスト」として、以下のように配列で与えられます：
　　{{1, 3}, {1, 4}, {3, 4}, {2, 4}, {4, 5}}

プログラムがやろうとしていること

この「辺のリスト」を「隣接行列」という別の形式に変換するプログラムが出題されています。

隣接行列とは：

頂点の数を N としたとき、N×N の表を作り、

• 「i行j列」の値が 1 → 頂点 i と 頂点 j がつながっている
• 「i行j列」の値が 0 → つながっていない

となる表（行列）です。無向グラフなので、adj[i][j] = adj[j][i] になります。

たとえば、頂点1と3がつながっていれば
adjMatrix[1][3] = 1 および adjMatrix[3][1] = 1 になります。

プログラムの解説

プログラムでは以下のことをしています：

1. 頂点の数 nodeNum に合わせて adjMatrix を全て0で初期化
2. 辺のリスト（edgeList）を1つずつ取り出して、
   • u ← edgeList[i][1]
   • v ← edgeList[i][2]
     で、uとvを結ぶ辺を表す。
3. この頂点uとvを結ぶ場所に1を設定する。

ここで空欄の部分に入るコードは：

• adjMatrix[u][v] ← 1
• adjMatrix[v][u] ← 1

です。

これにより、uとvをつなぐ両方向の情報が1に更新され、隣接行列として正しく反映されます。

解説

　　本問は、無向グラフの「辺のリスト」から「隣接行列」を作るプログラムにおいて、どこに1を代入すべきかを問う問題です。無向グラフでは、頂点uとvがつながっている場合、その両方向adjMatrix[u][v]とadjMatrix[v][u]の両方を1にする必要があります。

　これにより、どちらの方向から見ても「つながっている」と判断できます。選択肢エは、adjMatrix[u][v] ← 1 と adjMatrix[v][u] ← 1 の両方を正しく代入しており、隣接行列の性質を満たします。

　一方、他の選択肢では片方だけを1にする、または対角成分など間違った箇所に代入しており、隣接行列として成立しません。無向グラフであることをしっかり読み取るのが正解の鍵でした。

ア(adjMatrix[u, u] ← 1):
　これは頂点uと自身を結ぶループを意味してしまい、問題の無向グラフには不要です。
イ(adjMatrix[u, u] ← 1, adjMatrix[v, v] ← 1):
　どちらも自己ループを表すもので、グラフのつながりを正しく表現できません。
ウ(adjMatrix[u, v] ← 1):
　一方向の情報しか反映されておらず、無向グラフとしては不完全です。
オ(adjMatrix[v, u] ← 1):
　これも片方しか設定していないため、正しい隣接行列になりません。
カ(adjMatrix[v, v] ← 1):
　頂点vの自己ループになり、意図と異なります。

難易度

　この問題は、グラフ理論の基本である隣接行列の仕組みと無向グラフの性質（対称性）を理解しているかを問う内容です。配列の取り扱いやループ処理に慣れていればそれほど難しくはないため、難易度は「やや易しい」と言えます。ただし、配列の添字の使い方を正確に理解していないと間違えやすいため、基礎力が問われます。

スポンサーリンク

用語補足

無向グラフ：
頂点同士のつながり（辺）に方向がないグラフのことです。たとえば、AとBがつながっていれば、BとAもつながっているとみなされます。よって、隣接行列では対称性が必要になります。

隣接行列：
グラフの頂点間の接続関係を2次元配列（行列）で表したものです。行i列jの要素が1なら、頂点iとjの間に辺があることを意味します。無向グラフでは[i][j]と[j][i]の両方を1にします。

2次元配列：
行と列で構成される配列で、表やマトリックスのようにデータを並べる構造です。プログラミングでは多くの情報を効率的に管理・操作するためによく使用されます。

対策

　グラフ理論の基本である「隣接行列」や「無向グラフ」「辺の配列」の概念を正確に理解し、プログラムの処理フローに沿って手順を追えるようにしておくことが重要です。具体的には、配列の使い方や添字の扱いを正確に理解し、図からデータ構造に変換できる力を身につけることが有効です。