グラフ｜隣接行列の読み方と、深さ優先探索・幅優先探索【基本情報技術者試験科目B】

グラフは丸と線の絵で表されます。けれどもプログラムが扱うのは絵ではなく配列です。絵と配列を行き来できるようになれば、グラフのプログラムは2次元配列のプログラムとして読めます。

期間限定クーポンPR｜Udemy の講座科目B オリジナル模試 3回分・60問42%OFF 1,500円~~2,600円~~中身を見る ›

この回の内容を動画で見る

講義の実際の画面公開記念・いまだけ先着100名0円~~通常 2,600円~~有料講座「科目B 基礎講義」プログラムを1行ずつたどり、値がどう変わるかを動画で見せます。この回の講義もこの講座に入っています。講義の目次と無料の1本を見るUdemy・12月3日まで・100名に達したら通常価格に戻ります

次のページで講義の目次と無料の講義を見られます。受講ボタンとクーポンコードもそこにあります。

グラフ ── 頂点を辺で結んだもの
隣接のもち方 ── 辺の配列と隣接行列
1. 辺の配列から隣接行列を作る
隣接行列の読み方 ── 行を横に読むと、隣の頂点が並ぶ
たどり方 ── 深さ優先探索と幅優先探索
次に読む

グラフ ── 頂点を辺で結んだもの

グラフとは、いくつかの点と、点どうしを結ぶ線でできた図のことです。点を頂点、線を辺と呼びます。駅と線路、人と人のつながりのように、「どれとどれがつながっているか」を表すのに使います。折れ線グラフや棒グラフとは別のものです。

グラフの例 ── 頂点が5個、辺が5本

丸が頂点、線が辺。頂点には 1 から番号を付ける

頂点2 からは線が3本出ていて、相手は 1・3・5。頂点3 からは1本だけで、相手は 2。

線に矢印は付いていません。どちら向きにも通れるグラフです。

この図のように辺に向きが無いグラフを無向グラフ、辺が矢印になっていて一方向にしか通れないグラフを有向グラフといいます。ここから先は、この無向グラフ1つだけを使います。

隣接のもち方 ── 辺の配列と隣接行列

絵のままではプログラムで扱えないので、つながり方を配列に書き直します。書き方は2つあります。

同じグラフを、2つの形で持つ

どちらも、すぐ上の絵と同じグラフです。

辺の配列 ── 辺を1本ずつ、両端の番号で書いて並べる

整数型配列の配列: edges ← {{1, 2}, {1, 4}, {2, 3}, {2, 5}, {4, 5}}

{1, 2} が「頂点1 と頂点2 を結ぶ辺」。辺が5本なので、要素数は 5。

隣接行列 ── 辺があるマスに 1、無いマスに 0

	1	2	3	4	5
1	0	1	0	1	0
2	1	0	1	0	1
3	0	1	0	0	0
4	1	0	0	0	1
5	0	1	0	1	0

左の数字が行番号、上の数字が列番号で、どちらも頂点の番号。太枠の2マスが、辺 {1, 2} のぶん。

1つ目は、辺を1本ずつ並べる書き方です。令和6年度科目B 問3 では、これを辺の配列と呼んでいます。

2つ目が隣接行列です。同じ問3 は、こう定義しています。

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

隣接行列とは，グラフに含まれる頂点の個数と等しい行数及び列数の正方行列で，i 行j 列の成分は頂点i と頂点j を結ぶ辺があるときに1 となり，それ以外は0 となる。

頂点が5個なら5行5列の表です。「成分」は表のマス1つのことなので、1行2列のマスが 1 なら、頂点1 と頂点2 を結ぶ辺があると読みます。

無向グラフでは、頂点1 と頂点2 を結ぶ辺は、頂点2 と頂点1 を結ぶ辺でもあります。だから1本の辺は、1行2列と2行1列の2マスに 1 が入ります。

辺の配列から隣接行列を作る

辺の配列を先頭から1本ずつ取り出して、その辺のぶんの2マスに 1 を入れていけば、隣接行列ができます。隣接行列にしておくと、ある頂点とつながっている頂点を、表の1行を読むだけで調べられます。

整数型配列の配列: edges ← {{1, 2}, {1, 4}, {2, 3}, {2, 5}, {4, 5}}
整数型の二次元配列: adj ← {5行5列の 0}
整数型: i, u, v
for (i を 1 から edgesの要素数 まで 1 ずつ増やす)
  u ← edges[i][1]
  v ← edges[i][2]
  adj[u, v] ← 1
  adj[v, u] ← 1
endfor

当サイトで作った例です。型の名前と配列の書き方は、令和6年度科目B 問3 に合わせています。

上から読む

```
整数型配列の配列: edges ← {{1, 2}, {1, 4}, {2, 3}, {2, 5}, {4, 5}}
```
辺の配列。整数型配列の配列 は、配列を要素にもつ配列です。edges[1] が1本目の辺 {1, 2} で、edges[1][1] がその1つ目の番号の 1、edges[1][2] が2つ目の番号の 2 です。配列の中の配列なので、[ ] を2つ続けて書きます。
```
整数型の二次元配列: adj ← {5行5列の 0}
```
表を用意する。頂点が5個なので5行5列。中身は全部 0 で、ここへ 1 を入れていきます。
```
for (i を 1 から edgesの要素数 まで 1 ずつ増やす)
  u ← edges[i][1]
  v ← edges[i][2]
```
辺を1本取り出す。edgesの要素数 は辺の本数の 5 なので、5周します（頂点の個数と同じ 5 ですが、こちらは辺の本数です）。i 本目の辺の両端を u と v に入れます。
```
  adj[u, v] ← 1
  adj[v, u] ← 1
endfor
```
2マスに 1 を入れる。adj[u, v] は u 行 v 列のマスです。二次元配列は [行, 列] とカンマで区切って書きます。向きの無い辺なので、行と列を入れ替えた adj[v, u] にも入れます。

辺の配列から隣接行列を作る

当サイトオリジナルの例題

ループ開始前

作っている隣接行列 adj

▲ いま読んでいる▲ いま書いた

いま計算していること

まだ計算していません

変数の状態

トレース表（進めると1行ずつ積み上がります）

実行すると adj は、上の図の隣接行列と同じ表になります。1 は10個で、辺の本数のちょうど2倍です。

実際の出題にそのまま出ている

令和6年度科目B 問3 は、辺の配列を隣接行列に変換する関数の問題で、1 を入れる行が空欄になっています。問題文と解き方は令和6年度科目B 問3の解説にあります。

隣接行列の読み方 ── 行を横に読むと、隣の頂点が並ぶ

辺でつながっている相手の頂点を、ここでは隣と呼びます。隣接行列があれば、ある頂点の隣はその頂点の番号の行を横に読むだけで分かります。

2行目を横に読む ── 頂点2 の隣が分かる

色の付いたマス＝2行目で 1 が入っているマス

	1	2	3	4	5
1	0	1	0	1	0
2	1	0	1	0	1
3	0	1	0	0	0
4	1	0	0	0	1
5	0	1	0	1	0

1 が入っているのは 1列目・3列目・5列目。だから頂点2 の隣は 1・3・5。絵で頂点2 から出ていた3本の線の相手と同じです。

行番号が「いまいる頂点」、1 が入っている列番号が「そこから行ける頂点」。

プログラムでは、行番号を固定して、列番号だけを 1 から順に進めます。先ほど作った adj の2行目を読むなら、こう書けます。

整数型: j
for (j を 1 から 5 まで 1 ずつ増やす)
  if (adj[2, j] が 1 と等しい)
    jを出力
  endif
endfor

当サイトで作った例です。adj は、上のプログラムで作った隣接行列です。

出力は 1、3、5 の順です。adj[2, j] の 2 が「いまいる頂点」、j が「隣かどうかを調べる相手」です。j を進める上限の 5 は、頂点の個数です。

グラフのプログラムで最初に探す行

adj[k, j] のように行を固定して列を進めるくり返しがあれば、そこは「頂点 k の隣を1つずつ調べている」ところです。列を左から進めるので、隣は番号の小さい順に出てきます。

たどり方 ── 深さ優先探索と幅優先探索

ある頂点から出発して、辺をつたって行ける頂点を漏れなく1回ずつ訪れることを考えます。隣が2つ以上あるとき、どれを先に訪れるかの決め方が2つあります。

2つの決め方

深さ優先探索 ── 隣でまだ訪れていない頂点へすぐ進む。進める隣が無くなったら、来た道を戻って残りの隣を調べる。

幅優先探索 ── 出発点の隣を全部訪れてから、先に訪れた頂点から順に、その隣を全部訪れる。出発点に近い頂点から順になる。

どちらも、隣は隣接行列の行を左から読んで知ります。だから隣が2つ以上あれば、番号の小さいほうが先です。

同じグラフを、頂点1 から2通りにたどる

どちらも5個の頂点を1回ずつ訪れます。変わるのは順番だけです。箱の中の数字は頂点の番号です。

たどるグラフ（隣は、行を左から読む順＝番号の小さい順に見つかる）

深さ優先探索 ── 進めるだけ進み、行き止まりで戻る

進む

2へ戻る

進む

1 → 2 → 3 と進み、3 で行き止まり。2 へ戻って、残っていた 5 へ進み、4 へ。
訪れた順は 1 → 2 → 3 → 5 → 4。

幅優先探索 ── 出発点に近い頂点から順に訪れる

1の隣

2・4

2の隣

3・5

頂点1 の隣の 2 と 4 を両方とも訪れてから、2 の隣の 3 と 5 へ。
訪れた順は 1 → 2 → 4 → 3 → 5。

深さ優先は頂点4 が最後。幅優先は頂点4 が3番目。頂点4 は出発点のすぐ隣なのに、深さ優先では後回しになります。

次に読む

A14	AI・データを題材にしたプログラム
令和6年度問3	辺の配列を隣接行列に変換する ─ 実際の出題で確かめる
サンプル問題問9	2分木をたどって節番号を出力する出題
A3-1	2次元配列の走査 ─ 行と列の読み方
第2部	科目Bのアルゴリズム ─ 出るものの地図
目次	基本情報技術者試験科目B 攻略ガイド