令和6年度の科目B、問3です。用語が一気に4つ（グラフ・辺・隣接行列・二次元配列）出てきて、読む量は多い問題です。ただしプログラムは実質3行で、気づくところは1か所しかありません。この記事では、その1か所を見つけて、解答群に頼らずに空欄を書くところまで進みます。
出題
まず原文のまま読んでみてください。言葉と記号の読み方は次の節にまとめてありますので、読めなくてもここでは問題ありません。
出典：令和6年度 基本情報技術者試験 科目B 公開問題 問3
次のプログラム中の に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は1 から始まる。
図1 に示すグラフの頂点には，1 から順に整数で番号が付けられている。グラフは無向グラフであり，各頂点間には高々一つの辺がある。一つの辺は両端の頂点の番号を要素にもつ要素数2 の整数型の配列で表現できる。例えば，{1，3} は頂点1 と頂点3 を端点とする辺を表す。グラフ全体は，グラフに含まれる辺を表す要素数2 の配列を全て格納した配列（以下，辺の配列という）で表現できる。辺の配列の要素数はグラフの辺の個数と等しい。図1 のグラフは整数型配列の配列{{1, 3}, {1, 4}, {3, 4}, {2, 4}, {4, 5}}と表現できる。
図1 グラフの例
※ 図1 は原本では絵（頂点 1〜5 を線で結んだもの）ですが、絵そのものは引用していません。同じグラフを、次の次の節で当サイトが描いています。すぐ上の一文にあるとおり、この絵の中身は辺の配列そのものです。
関数edgesToMatrix は，辺の配列を隣接行列に変換する。隣接行列とは，グラフに含まれる頂点の個数と等しい行数及び列数の正方行列で，i 行j 列の成分は頂点i と頂点j を結ぶ辺があるときに1 となり，それ以外は0 となる。行列の対角成分は全て0 で，無向グラフの場合は対称行列になる。図1 のグラフを表現する隣接行列を図2 に示す。
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
図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]
endfor
return adjMatrix
解答群
ア adjMatrix[u, u] ← 1
イ adjMatrix[u, u] ← 1 adjMatrix[v, v] ← 1（2行）
ウ adjMatrix[u, v] ← 1
エ adjMatrix[u, v] ← 1 adjMatrix[v, u] ← 1（2行）
オ adjMatrix[v, u] ← 1
カ adjMatrix[v, v] ← 1
答えだけ先に見る
正解は エ（adjMatrix[u, v] ← 1 と adjMatrix[v, u] ← 1 の2行）です。
この問題に出てくる言葉と記号
読めないものがあったときだけ開いてください。この問題に出てくるものは、ここに全部あります。
言葉と記号の読み方をひらく
| 書き方・言葉 | 読み方 |
|---|---|
| グラフ・頂点・辺 | 点（頂点）を線（辺）で結んだ図のこと。ここでは頂点に 1〜5 の番号が付いています。折れ線グラフのことではありません |
| 無向グラフ | 辺に向きが無いグラフ。頂点1 から頂点3 へと頂点3 から頂点1 へを区別しません |
| 辺の配列 | 辺を全部並べたもの。{1, 3} が1本の辺（頂点1 と頂点3 を結ぶ）で、それを5本ぶん並べたのが {{1, 3}, {1, 4}, {3, 4}, {2, 4}, {4, 5}} |
| 隣接行列 | 「どの頂点とどの頂点がつながっているか」を 0 と 1 で表した正方形の表。頂点が5個なら5行5列 |
| 対角成分 | 1行1列・2行2列・… と、行と列の番号が同じところ。左上から右下への斜めの並びです |
| 対称行列 | その斜めの線を折り目にすると、ぴったり重なる表のこと |
整数型の二次元配列 |
行と列のある表。1次元の配列が1列に並ぶのに対して、こちらは縦横に並びます。指すときは [行, 列] とカンマ（この問題の adjMatrix） |
整数型配列の配列 |
配列を要素にもつ配列。「辺（要素数2の配列）」が5本ぶん並んだもの（この問題の edgeList）。指すときは [i][1] と角括弧を2段。表（二次元配列）とは書き方が違います |
adjMatrix[u, v] |
表のu 行 v 列の箱。カンマの前が行、後ろが列です |
edgeList[i][1] |
edgeList[i] で i 本目の辺を取り出し、さらに [1] でその1つ目の番号を取り出す、という二段構えです |
← |
右のものを、左に入れるという印。u ← 3 なら「u に 3 を入れる」。等号（比べる）ではありません |
for (…)endfor |
同じ処理を、決められた回数くり返す。endfor まで来たら for の行へ戻り、次の回に進みます |
return ◯ |
◯ を返して、その関数はそこで終わり。返したものが、呼んだ側の答えになります |
| 関数・引数 | 関数＝ひとまとまりの処理に名前を付けたもの。引数＝それを呼ぶときに外から渡す値（ここでは辺の配列と、頂点の個数） |
| 成分 | 表のマス1つのこと。「i 行 j 列の成分」＝i 行 j 列のマス |
| 高々一つ | あっても1つ、多くても1つという意味。同じ2つの頂点を結ぶ辺が2本ある、ということは起きません |
記号でつまずいたら、下の教科書から、先にそこだけ読んでください（G9-1 のような番号は、当サイトの擬似言語の教科書の第何回かを表します）。
[行, 列] で1つの箱を指すG6-1繰返し for ─ 1から要素数まで、1ずつG4-1配列と要素番号 ─ 要素番号は 1 からG2-3代入 ─ ← は「右のものを左に入れる」同じつながりを、絵と表で見る
まず、この問題のグラフです。点が頂点、線が辺。頂点は 1 から 5 の5個で、線は5本あります。
この問題のグラフ（頂点5個・辺5本）
※ この絵は、原文が併記している辺の配列から当サイトで描いたものです（原本の図1 と同じグラフですが、絵そのものの引用ではありません）。
辺の配列 {1, 3} {1, 4} {3, 4} {2, 4} {4, 5} を、そのまま線にしたもの
1
2
3
4
5
頂点4 には線が4本集まっています。頂点2 と頂点5 は1本ずつ。この本数は、あとで表と見比べるときの手がかりになります。
線に向きは付いていません。
これが無向グラフです。{1, 3} は「1 と 3 がつながっている」という意味で、1 から 3 と、3 から 1 を区別しません。
同じつながりを表にしたのが、出題の図2 です。頂点が5個なので5行5列、マスは25個。1 が立っているマスだけが「つながっている」を表します。原文の定義は 「i 行j 列の成分は頂点i と頂点j を結ぶ辺があるときに1 となり，それ以外は0 となる」。
図2 を、1マスずつ読む
0 と 1 が並んでいるだけの表ですが、読み方は1つだけです。
琥珀＝いま読むマス（ここでは1行3列）
| 1 | 2 | 3 | 4 | 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行3列は 1。だから頂点1 と頂点3 を結ぶ辺がある、と読みます（辺の配列の1本目が {1, 3}）。4行目を見ると 1 が4個で、絵で頂点4 に線が4本集まっていたのと合っています。
いっぽう左上から右下への斜めの並び（1行1列・2行2列・…）は、5つとも 0 ── 頂点は自分自身と辺を持たないからです（原文の「対角成分は全て0」）。
1 が立っているマス ＝ その行の頂点と、その列の頂点が、辺でつながっている。
※ 行番号と列番号は当サイトで付けたものです。原本の図2 に番号は書かれていません。
図2 の 1 を、数えてみる
ここが、この問題で唯一の気づきどころです。先に、図2 の 1 が何個あるか数えてみてください。
10個ありましたか。辺は5本しかないのに、その2倍です。どこで倍になったのかを、置いて確かめます。1本の辺の1つ目の番号を u、2つ目を v と呼ぶことにします（プログラムでも同じ名前が使われています）。{1, 3} なら u は 1、v は 3。まずは素直に、前の番号を行、後ろの番号を列にして置いてみます ── この5本を「u 行 v 列」に置くと、図2 になるでしょうか。
辺を「u 行 v 列」に置いていくと、どうなるか
辺の配列は {1, 3} {1, 4} {3, 4} {2, 4} {4, 5} の5本。太枠＝いま置いたマス／緑＝それでは足りなかったマス。②の矢印は、灰の斜線（折り目）をはさんだ相手を指しています（同じ番号どうしが1本の辺です）。
① 5本を u 行 v 列 に1つずつ置いた
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 |
0 |
1 |
1 |
0 |
| 2 | 0 |
0 |
0 |
1 |
0 |
| 3 | 0 |
0 |
0 |
1 |
0 |
| 4 | 0 |
0 |
0 |
0 |
1 |
| 5 | 0 |
0 |
0 |
0 |
0 |
{1, 3} は1行3列、{1, 4} は1行4列 …と置きました（太枠の5マス。番号は辺の何本目か）。1 は5個。辺の本数と同じです。
② こちらが図2（出題に載っている表）
| 1 | 2 | 3 | 4 | 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 |
太枠は、①で置いた5個。そのまま入っています。そのうえで、緑の5個がさらに立っています ── ①の置き方では足りていなかった、ということです。
矢印は5本とも、折り目に直角。1本の辺は、折り目をはさんだ2か所に立ちます。
理由は、さきほどの絵です。線に向きが無いのだから、辺 {1, 3} は「頂点1 から頂点3」であると同時に「頂点3 から頂点1」。だから表では 1行3列と 3行1列の2か所に立ち、折り目で折るとぴったり重なります ── これが、原文の「無向グラフの場合は対称行列になる」の意味です。
ここが分かれば、この問題は終わりです。あとは「2か所に書く」を、プログラムの言葉に直すだけになります。
コードの中で、空欄は「この辺のぶんを書き込む」行
いま分かったことを、プログラムの各行に当てはめます。
○整数型の二次元配列: edgesToMatrix(整数型配列の配列: edgeList, 整数型: nodeNum)
辺の配列と頂点の個数を受け取り、二次元配列（＝行列）を返す関数
整数型の二次元配列: adjMatrix ← {nodeNum行nodeNum列の 0}
答えを書き込む表を、先に用意する。5行5列で、中身は全部 0。ここから1 を立てていく
整数型: i, u, v
この3つは入れ物だけ用意する（値はまだ）
for (i を 1 から edgeListの要素数 まで 1 ずつ増やす)
辺を1本ずつ取り出す。辺は5本なので5周
u ← edgeList[i][1]
edgeList[i] が i 本目の辺。その 1つ目の番号を u へ
v ← edgeList[i][2]
同じ辺の 2つ目の番号を v へ。これでいま見ている辺の両端が u と v
ここが空欄。この1本の辺を、表のどこに書き込むかを決める
endfor
次の辺へ。5本ぶん終わったら抜ける
return adjMatrix
できあがった表を返す
※ 右側の注釈は当サイトで書き加えたものです。プログラム自体は原文のまま引用しています。
空欄に入るものを決める
決めるのは、この3行のいちばん下です。
〔プログラム〕辺の両端を取り出してから、空欄へ
u ← edgeList[i][1]
v ← edgeList[i][2]
※ 上の〔プログラム〕からの抜粋です（1字も変えていません）。
1本目の辺で考えます。edgeList[1] は {1, 3} なので、u は 1、v は 3。さきほど見た2か所を u・v の言葉に置きかえるだけです ── u 行 v 列と、v 行 u 列。行と列を入れ替えたものを、もう1行書くということです。
空欄に入るもの
adjMatrix[u, v] ← 1adjMatrix[v, u] ← 1
ここで解答群と照らす
この2行がそろっているのは、解答群では エ ひとつだけです。
答え合わせ ── 5本ぶん書き込むと、図2 になる
空欄に エ を入れて、辺を5本とも書き込んでみます。できあがった表が図2 と同じかどうかを見てください。
1行ずつ追う 正解の エ（[u, v] と [v, u] の2行）
出典：令和6年度 科目B 公開問題 問3（空欄に エ を入れたもの）
ループ開始前
配列
いま計算していること
変数の状態
return で返した表
トレース表（進めると1行ずつ積み上がります）
正解は エ
adjMatrix[u, v] ← 1 と adjMatrix[v, u] ← 1。1本の辺につき2か所書くので、5本で 1 が10個立ち、図2 と1マスも違わない表ができます。
ほかの5つは、ここまでに見た2つの事実で外れます。ア（[u, u]）・イ（[u, u] と [v, v]）・カ（[v, v]）は行と列に同じ番号を書くので、1 が立つのは斜めの並びだけ ── そこは必ず 0 でした。ウ（[u, v]）とオ（[v, u]）は1本につき1か所しか書かないので、5本ぶんでも 1 は5個どまり ── まさに、さきほど「置いてみた」ときの表です。どちらも折り目の片側しか埋まらないので、対称になりません。
次に読む
この問題でどこに手間取ったかで、行き先が変わります。
[行, 列] の指し方があやふやだった人へG2-3代入「←」 ── 「入れる」と「等しい」の区別でつまずいた人へG6-1繰返し for ── i が増えていく感じがつかめなかった人へ一覧科目B 全44問の解説 ── 続けて解きたい人へこの記事で引用した資料
いずれも独立行政法人情報処理推進機構（IPA）が公表したものです。IPAは公表済みの試験問題について、教育目的での使用に許諾および使用料を不要としていますが、著作権は放棄していません。本記事では問題文を改変せずに引用しています。
