回 6-3 分野 6 ベクトルと行列
隣接行列は、頂点が n 個のグラフを n 行 n 列の表で表し、頂点 i から j へ辺があれば (i, j) 成分を 1、無ければ 0 にした物です。向きの無いグラフでは表が左上から右下の斜めについて対称になり、行の和がその頂点の次数 (つながる辺の数) になります。次数を全部足すと、辺の数のちょうど 2 倍です。辺が少ないグラフでは、つながる相手だけを並べる隣接リストのほうが記憶を使いません。
同じグラフを隣接リストと隣接行列の 2 つの形で持ち、次数、辺の数、2 歩の道の数を Python で数えて確かめます。
文 ゆめさくコード編集部公開 2026年10月30日更新 2026年10月30日出典を確かめた日 2026年10月30日
つながりを、プログラムはどう覚えるのか
路線図、SNS のフォロー、ライブラリの依存関係は、どれも「点と、点をつなぐ線」でできています。これをグラフと呼びます。プログラムで扱うには、図ではなく、数の形で持つ必要があります。
一番まっすぐな形が隣接行列です。点が n 個なら n 行 n 列の表を作り、点 i と点 j がつながっていれば (i, j) に 1、いなければ 0 を書きます。もう 1 つの形が隣接リストで、点ごとに、つながる相手だけを並べます。
この回では、同じグラフを 2 つの形で持ち、次数と辺の数の決まりと、行列の積で道を数える方法を、Python で数えて確かめます。
グラフ、次数、2 つの持ち方
頂点と辺
グラフの点を頂点、線を辺と呼びます。辺に向きが無いグラフを無向グラフ (友だちの関係、道路)、向きがあるグラフを有向グラフ (フォロー、依存関係、一方通行) と呼びます。
この回では、次の 5 つの頂点と 6 本の辺の無向グラフを例にします。頂点は 0 から 4 の番号で呼びます。
| 番号 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|
| 辺 | 0-1 | 0-2 | 1-2 | 1-3 | 2-3 | 3-4 |
|---|
隣接行列の作り方
頂点 i と j の間に辺があれば、(i, j) と (j, i) の両方に 1 を書きます。上の例の隣接行列は次の通りです。
| 0 | 1 | 2 | 3 | 4 |
|---|
| 0 | 0 | 1 | 1 | 0 | 0 |
|---|
| 1 | 1 | 0 | 1 | 1 | 0 |
|---|
| 2 | 1 | 1 | 0 | 1 | 0 |
|---|
| 3 | 0 | 1 | 1 | 0 | 1 |
|---|
| 4 | 0 | 0 | 0 | 1 | 0 |
|---|
無向グラフでは、左上から右下の斜め (対角) を境に、表が対称になります。対角の数は、頂点が自分自身につながる辺 (ループ) があるかを表し、この例では全部 0 です。
次数と、辺の数との関係
頂点につながる辺の数を、その頂点の次数と呼びます。隣接行列では、その頂点の行の和が次数です。頂点 1 の行は 1, 0, 1, 1, 0 で、次数は 3 です。
次数を全部足すと、辺の数のちょうど 2 倍になります。1 本の辺は両端の 2 つの頂点の次数に 1 ずつ数えられるからです。この例では次数が 2, 3, 3, 3, 1 で、和は 12、辺は 6 本です。
だから、ループの無い無向グラフの隣接行列から辺の数を出すには、1 の数を全部数えて 2 で割るか、対角より右上 (上三角) の 1 だけを数えます。
ループを含めるときは、決まりに注意が要ります。
無向グラフでは、ループを 1 本で次数を 2 増やすと数え、隣接行列の対角に 2 と書く決まりがよく使われます。そうすると、行の和が次数になり、「次数の和 = 辺の数 × 2」もそのまま成り立ちます。有向グラフでは 1 と書くことが多く、どちらにするかは本や道具によって違います。
有向グラフの隣接行列
有向グラフでは、i から j への辺があるときだけ (i, j) を 1 にします。表は対称とは限りません。行の和はその頂点から出る辺の数 (出次数)、列の和は入る辺の数 (入次数) です。出次数の和と入次数の和は、どちらも辺の数に等しくなります。
重み付きのグラフ
辺に距離や料金のような重みがある場合は、1 の代わりに重みを書きます。辺が無い所は、0 と区別するために、無限大や None を書くことが多いです。最短経路の探索 (ダイクストラ法) は、この重みの表か、重み付きの隣接リストを使います。
隣接リストとの使い分け
隣接リストは、頂点ごとに、つながる相手だけを並べた形です。上の例なら、0 は [1, 2]、1 は [0, 2, 3] です。
| 比べる点 | 隣接行列 | 隣接リスト |
|---|
| 記憶の量 | 頂点数 n の 2 乗 | 頂点数 + 辺の数 × 2 (無向) |
|---|
| i と j がつながるかを調べる | 表の 1 か所を見るだけ | i の相手を順に見る |
|---|
| i の相手を全部たどる | 行の n 個を全部見る | 相手の数だけ見る |
|---|
| 向く場面 | 頂点が少ない、辺が多い | 頂点が多く、辺が少ない |
|---|
SNS や路線のように、頂点は多いが 1 つの頂点の相手は少ないグラフでは、隣接リストのほうが記憶も手間も少なく済みます。
隣接行列の積で、道の数を数える
隣接行列 A を 2 回掛けた A² の (i, j) 成分は、i から j へちょうど 2 本の辺でたどる道 (同じ頂点を通ってもよい) の数です。A の i 行目と j 列目の内積は、「i から k への辺」と「k から j への辺」が両方ある k の数を数えているからです。A を k 回掛ければ、ちょうど k 歩の道の数になります。
動かして確かめる
1 本目は、辺の一覧から、隣接リストと隣接行列の両方を作ります。次数の和が辺の数の 2 倍になるか、表が対称かも確かめます。
動かす 2 つの形で持ち、次数を数える
実行すると、次の通りに出ます
[0, 1, 1, 0, 0]
[1, 0, 1, 1, 0]
[1, 1, 0, 1, 0]
[0, 1, 1, 0, 1]
[0, 0, 0, 1, 0]
0 の相手 [1, 2]
1 の相手 [0, 2, 3]
2 の相手 [0, 1, 3]
3 の相手 [1, 2, 4]
4 の相手 [3]
次数 [2, 3, 3, 3, 1]
和 12 辺 6
対称 True
上三角の 1 6
隣接行列は上の表と同じで、隣接リストは頂点ごとの相手の並びです。次数は 2, 3, 3, 3, 1 で、和は 12、辺の 6 本のちょうど 2 倍です。表は対称で、上三角の 1 を数えると辺の数 6 が出ます。
2 本目は、有向グラフです。行の和が出次数、列の和が入次数になり、どちらの合計も辺の数になるかを確かめます。依存関係を例にし、「a は b を使う」を a から b への辺にします。
動かす 有向グラフの出次数と入次数
実行すると、次の通りに出ます
app 出 2 入 0
web 出 2 入 1
db 出 1 入 2
log 出 0 入 2
5 5 5
app は 2 つを使い、誰にも使われていません。log は 2 つから使われ、何も使いません。出次数の和と入次数の和はどちらも 5 で、辺の数と同じです。入次数が 0 の app から順に起動の順を決めるような処理 (トポロジカルソート) は、この入次数から始めます。
3 本目は、隣接行列を 2 回掛けて、2 歩の道の数を数えます。1 本目と同じ 5 つの頂点のグラフです。
動かす 行列の 2 乗で 2 歩の道を数える
実行すると、次の通りに出ます
[2, 1, 1, 2, 0]
[1, 3, 2, 1, 1]
[1, 2, 3, 1, 1]
[2, 1, 1, 3, 0]
[0, 1, 1, 0, 1]
0 から 3 2
対角 [2, 3, 3, 3, 1]
A² の (0, 3) は 2 で、0 から 3 へ 2 歩で行く道は 0→1→3 と 0→2→3 の 2 本です。対角の数 2, 3, 3, 3, 1 は次数と同じです (ループが無いグラフの場合)。i から出て i に戻る 2 歩の道は、相手へ行って戻る道なので、相手の数 (次数) だけあるからです。
4 本目は、頂点が多く辺が少ないグラフで、2 つの形の記憶の量を数で比べます。頂点が 1 万、1 つの頂点の相手が平均 10 の無向グラフとします。
動かす 記憶の量を比べる
実行すると、次の通りに出ます
辺 50000
行列のます 100000000
リストの数 110000
倍 909
辺は 5 万本です。隣接行列は 1 億個のますを使い、そのほとんどが 0 です。隣接リストは頂点 1 万と、辺 1 本につき両端で 2 つの合わせて 11 万個で済み、約 900 倍の差です。
隣接行列だけで考えると外れる所
頂点が多いと、表が大きすぎる
隣接行列の大きさは頂点数の 2 乗です。頂点が 100 万なら 1 兆個のますになり、普通の計算機の記憶には載りません。辺が少ないグラフは、隣接リストか、1 の場所だけを覚える疎行列の形で持ちます。
頂点の番号と、表の行の番号を取り違える
試験の問題でも、コードでも、頂点の名前と表の何行目かの対応を取り違える誤りが多い所です。プログラムでは、2 本目のように名前から番号への辞書を 1 つ作り、全部の場所でそれを通します。数学の本では頂点を 1 から数えることが多く、Python のリストは 0 から数えることにも注意します。
ループと二重の辺の決まりは、本や道具で違う
自分自身への辺 (ループ) や、同じ 2 つの頂点の間の 2 本目の辺 (多重辺) を、隣接行列でどう書くかは決まりによって違います。ループの対角を 1 と書くと、行の和と「次数の和 = 辺の数 × 2」がずれます。使う本や道具の決まりを先に確かめます。
仕事と試験でどう使うか
隣接行列と隣接リストを使う場面は、次の通りです。
- 経路探索。地図や路線の最短経路を、重み付きの隣接リストとダイクストラ法で求める
- 依存関係。パッケージやタスクの依存を有向グラフで持ち、入次数 0 の物から順に処理して、起動やビルドの順を決める。循環 (お互いに依存) があれば順が決まらないことも、同じ処理で見つかる
- SNS とつながりの分析。フォローを有向グラフにし、入次数の多い人、2 歩で届く人 (知り合いの知り合い) を数える
- 基本情報技術者試験の対策。対策の頁では、隣接行列から図を選ぶ、辺の本数を答える形の問題がよく取り上げられる。ループの無いグラフなら、上三角の 1 を数える、対称を見る、の 2 つで多くが解ける。対角に数がある問題では、ループの決まりを先に読む
- グラフを使う機械学習。頂点のつながりを隣接行列で渡し、隣の頂点の情報を行列の積で集める
よくある問い
隣接行列はどうやって作りますか
頂点に 0 から n − 1 の番号を付け、n 行 n 列の全部 0 の表を作ります。辺 (i, j) ごとに (i, j) を 1 にし、無向グラフなら (j, i) も 1 にします。重みがあれば 1 の代わりに重みを書きます。
隣接行列から辺の数はどう数えますか
無向グラフでループが無ければ、1 の数を全部数えて 2 で割るか、対角より右上の 1 だけを数えます。有向グラフなら、1 の数がそのまま辺の数です。
隣接行列と隣接リストはどちらを使えばよいですか
頂点が少ないか、ほとんどの頂点の組がつながっているなら隣接行列、頂点が多く辺が少ないなら隣接リストです。「i と j がつながるか」をとても多く調べるなら隣接行列が速く、相手を順にたどる処理 (幅優先探索やダイクストラ法) なら隣接リストが向きます。
隣接行列が対称にならないのはなぜですか
有向グラフだからです。i から j への辺があっても、j から i への辺があるとは限らないので、(i, j) と (j, i) が違ってよいです。無向グラフで対称にならなければ、片方を書き忘れています。
確認クイズ
答えだと思う選択肢を押すと、その場で正誤と理由が開きます。3 問すべてに正しく答えると、この回は修了で、石が緑に変わります (この端末のブラウザに残ります)。間違えた問いは、あとから解き直せます。
1 問目
ループの無い無向グラフで、頂点の次数が 1, 2, 2, 3, 4 でした。辺は何本ですか。
2 問目
有向グラフの隣接行列で、頂点 2 の列 (縦の並び) の 1 の数が表すのはどれですか。
3 問目
このコードを動かすと何が出ますか。
A = [[0, 1, 1],
[1, 0, 1],
[1, 1, 0]]
print(sum(map(sum, A)) // 2)
説明課題
「頂点が 100 万、1 人あたりのつながりが平均 100 の SNS のつながりを持つのに、隣接行列ではなく隣接リストを選ぶ理由」を、記憶の量の数を使って 3 文で説明してください。書いたら、下の模範解答を開いて比べてください。
模範解答
自分の説明を書いてから開いて、比べてください。
隣接行列は頂点数の 2 乗のますを使うので、100 万の 2 乗で 1 兆個になり、そのほとんどがつながっていないことを表す 0 になる。隣接リストは、つながりがある所だけを持つので、頂点 100 万と、1 人あたり 100 の相手の 1 億個ほどで済む。差は約 1 万倍で、相手を順にたどる処理も相手の数だけ見れば済むので、隣接リストを選ぶ。
つながりを表で持つか、相手の一覧で持つかを、頂点と辺の数から選べると、経路探索や依存関係の処理の速さと記憶の量を見積もれます。いまの自分が転職までの道のどの段にいるかは、転職診断で確かめられます。
もっと深く
この回の続きを、ゆめさくのコースの章や道具で深められます。頁の中の確認クイズに答えたあと、手を動かす量を増やしたいときに使ってください。
一次資料
どれも 2026年10月30日に開いて、題と中身を確かめました。
