次のプログラム中の に入れる正しい答えを、解答群の中から選べ。ここで、配列の要素番号は1から始まる。 図1に示すグラフの頂点には、1から順に整数で番号が付けられている。グラフは無向グラフであり、各頂点間には高々一つの辺がある。一つの辺は両端の頂点の番号を要素にもつ要素数2の整数型の配列で表現できる。例えば、{1, 3}は頂点1と頂点3を端点とする辺を表す。グラフ全体は、グラフに含まれる辺を表す要素数2の配列を全て格納した配列(以下、辺の配列という)で表現できる。辺の配列の要素数はグラフの辺の個数と等しい。図1のグラフは整数型配列の配列{{1, 3}, {1, 4}, {3, 4}, {2, 4}, {4, 5}}と表現できる。(図1: グラフの例。以下は図の構造の説明。) 関数edgesToMatrixは、辺の配列を隣接行列に変換する。隣接行列とは、グラフに含まれる頂点の個数と等しい行数及び列数の正方行列で、i行j列の成分は頂点iと頂点jを結ぶ辺があるときに1となり、それ以外は0となる。行列の対角成分は全て0で、無向グラフの場合は対称行列になる。図1のグラフを表現する隣接行列を図2に示す。 関数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] endfor return adjMatrix

無向グラフの隣接行列は対称。両方向の成分を1にする

頻出基本情報技術者試験／2024年度 公開問題 科目B 問3／アルゴリズムとプログラミング / データ構造

図1: グラフの例。無向グラフで頂点は1〜5の5個の丸で表される。辺は、頂点1と頂点3の間、頂点1と頂点4の間、頂点3と頂点4の間、頂点2と頂点4の間、頂点4と頂点5の間の5本。頂点4を中心にして頂点1・2・3・5とつながる形で、さらに頂点1と頂点3の間にも辺がある(1-3-4が三角形を形成し、4から2と5がそれぞれ枝分かれ)。 図2: 図1のグラフを表現する隣接行列（5行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
図1: グラフの例。無向グラフで頂点は1〜5の5個の丸で表される。辺は、頂点1と頂点3の間、頂点1と頂点4の間、頂点3と頂点4の間、頂点2と頂点4の間、頂点4と頂点5の間の5本。頂点4を中心にして頂点1・2・3・5とつながる形で、さらに頂点1と頂点3の間にも辺がある(1-3-4が三角形を形成し、4から2と5がそれぞれ枝分かれ)。 図2: 図1のグラフを表現する隣接行列（5行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

選択肢

正解と解説

正解：エ adjMatrix[u, v] ← 1 adjMatrix[v, u] ← 1

隣接行列では、頂点uと頂点vを結ぶ辺があるときにu行v列を1にする。無向グラフなので辺に向きはなく、行列は対称になるためv行u列も同時に1にしなければならない。片方だけでは対称行列にならず、図2の隣接行列を再現できない。

選択肢ごとの解説

出典：令和6年度 公開問題 基本情報技術者試験 科目B 問3（IPA）

同じ分野の他の問題

最終更新：2026-08-25／解説・選択肢ごとの解説は資格暗記が独自に作成しています。問題文と選択肢の出典は上記のとおりです。