グラフ表現とは（全体像）
グラフ表現は、「どの点とどの点がつながっているか」をコンピュータの中でどう記録するかの方法のこと。グラフ理論（点と線でつながりを表す数学）を、実際のデータ構造に落とし込む話だ。
代表的なのは2つ。
- 隣接行列 … 全部の点×全部の点の表（マス目）を作り、「つながっていれば1、いなければ0」を入れる。
- 隣接リスト … 各点ごとに「自分とつながっている点の一覧（リスト）」を持つ。
どちらも同じグラフを表せるが、得意・不得意（メモリと速さのバランス）が違うので、グラフの性質に合わせて選ぶ。
詳しく：行列とリストの使い分けだけ覚えれば戦える
ここが記事の心臓部。2方式を並べて比べる。
隣接行列と隣接リストの違い
| 隣接行列 | 隣接リスト | |
|---|---|---|
| 持ち方 | 点×点の表（マス目） | 各点ごとの隣の点リスト |
| 辺の有無の判定 | 速い（一発・O(1)） | リストをたどる（O(次数)） |
| メモリ | 多い（O(n²)） | 少ない（O(V+E)） |
| 向くグラフ | 密（線が多い） | 疎（線が少ない） |
いちばん大事なのが、使い分け。隣接行列は「2点がつながっているか」を一発で判定できる反面、点が多いと表が大きくなりすぎる（O(n²)）。隣接リストはメモリに優しいが、つながりを調べるにはリストをたどる必要がある。
だから、線が多い密なグラフは隣接行列、線が少ない疎なグラフは隣接リストが向く。SNSの友だち関係のように「点はたくさんあるが線は限られる」場合は疎グラフなので、隣接リストが基本だ。
「どちらも同じで選ぶ必要はない」「いつもリストが上」と思うのは誤りで、グラフの性質で使い分けるのがポイントだ。
わかりやすく言い換えると
要するに、グラフ表現は「つながりの持ち方の選び方」だ。
①隣接行列 … 全員ぶんの大きな出席表。「AとBは知り合い？」を表の交点で一発確認できるが、人数が多いと表が巨大になる
②隣接リスト … 各人が自分の友だちリストだけを持つ。場所を取らないが、「AとBは知り合い？」はAのリストをたどって確認する
つまり、つながりがぎっしり（密）なら表（行列）、まばら（疎）なら友だちリスト（リスト）が向く、というわけだね。
試験のツボ
🔴 一番出る：密なら行列・疎ならリスト
①密なグラフ（線が多い）は隣接行列が向く
②疎なグラフ（線が少ない）は隣接リストが向く
🔴 次に出る：それぞれの得意・不得意
①隣接行列＝辺判定が一発（O(1)）だがメモリO(n²)
②隣接リスト＝メモリO(V+E)で優しいが辺判定はたどる
🟡 押さえると安定：どちらも同じグラフを表せる
①表し方が違うだけで、同じグラフを表現できる
②使い分けはメモリと速さのバランスで決める
よくある間違い
①「隣接行列と隣接リストはまったく同じで、選ぶ必要はない」→ ✗ メモリと速さのバランスが違うので、グラフの性質で使い分ける。
②「隣接リストはつねに隣接行列より優れている」→ ✗ 密なグラフ（線が多い）では隣接行列のほうが有利なことがある。
③「隣接行列はメモリが少なくて済む」→ ✗ 隣接行列はO(n²)でメモリを多く使う。少ないのは隣接リスト。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（使い分け）
グラフ表現の使い分けに関する次の記述のうち、正しいものはどれか。
- 線が多い密なグラフは隣接リスト、線が少ない疎なグラフは隣接行列が向く
- どんなグラフでも隣接リストが最も優れているので、行列は使う必要がない
- 線が多い密なグラフは隣接行列、線が少ない疎なグラフは隣接リストが向く
- グラフの性質とは無関係に、表現方法はランダムに選んでよいものである
解答は 3 だよ。
線が多い密なグラフは隣接行列、線が少ない疎なグラフは隣接リストが向くんだ。グラフの性質（密か疎か）で使い分けるのがポイントだよ。
選択肢1は行列とリストが逆。選択肢2は「いつもリストが上」が誤り。選択肢4は「ランダムに選ぶ」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 行列とリストが逆 |
| 2 | ✗ | 密グラフは行列が有利 |
| 3 | ✓ | 密は行列・疎はリスト |
| 4 | ✗ | 性質で使い分ける |
オリジナル問題2（隣接行列の特徴）
隣接行列に関する次の記述のうち、正しいものはどれか。
- 辺の有無を一発で判定できるが、メモリをO(n²)と多く使う表現である
- 辺の有無は判定できないが、メモリをほとんど使わない表現のことである
- メモリをO(V+E)しか使わず、疎なグラフに最も向いている表現である
- 各点が自分の隣の点のリストを持つ、メモリに優しい表現のことである
解答は 1 だよ。
隣接行列は辺の有無を一発で判定できる（O(1)）けれど、メモリをO(n²)と多く使うんだ。だから線が多い密なグラフに向いているよ。
選択肢2は「判定できない」が誤り。選択肢3・4は隣接リストの説明だよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 一発判定だがメモリO(n²) |
| 2 | ✗ | 辺判定はできる |
| 3 | ✗ | それは隣接リスト |
| 4 | ✗ | それは隣接リスト |
オリジナル問題3（隣接リストの特徴）
隣接リストに関する次の記述のうち、正しいものはどれか。
- 点×点の表で持つため、メモリをO(n²)と多く使う表現のことである
- グラフを表現できず、つながりを記録することはできない方法である
- すべてのグラフで隣接行列より必ず遅く、使う意味がない表現である
- 各点が隣の点のリストを持ち、メモリO(V+E)で疎なグラフに向く
解答は 4 だよ。
隣接リストは各点が「隣の点のリスト」を持ち、メモリはO(V+E)で優しいんだ。だから線が少ない疎なグラフ（SNSの友だち関係など）に向いているよ。
選択肢1は「点×点の表・O(n²)」で隣接行列の説明。選択肢2は「表現できない」が誤り。選択肢3は「必ず遅い・使う意味がない」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | それは隣接行列 |
| 2 | ✗ | グラフを表現できる |
| 3 | ✗ | 疎グラフでは有利 |
| 4 | ✓ | 隣の点リスト・O(V+E)で疎グラフ向き |
まとめ
押さえどころ
- 🔴 使い分け ＝ 密なグラフ（線が多い）は隣接行列、疎なグラフ（線が少ない）は隣接リスト。
- 🔴 得意・不得意 ＝ 隣接行列は辺判定が一発（O(1)）だがメモリO(n²)、隣接リストはメモリO(V+E)だが辺判定はたどる。
- 🟡 共通点 ＝ どちらも同じグラフを表せる。メモリと速さのバランスで選ぶ。
次に学ぶ
- グラフ理論（最小全域木・最短経路） ── 隣接行列・リストで表したグラフ上で動くアルゴリズム（最短経路など）。表現と処理がつながる。
- 探索アルゴリズム（BFS・DFS・2分） ── グラフ表現の上で動くBFS・DFS。表現の選び方が探索の効率に効く。
執筆: SikakuQuest編集部