グラフ理論とは（全体像）
グラフ理論とは、点（頂点・ノード）と、それをつなぐ線（辺・エッジ）でできた「つながり」を扱う数学のことだ。
たとえば、駅（点）と路線（線）の地図、SNSの友だち関係、交通網などは、すべて「点と線のつながり」で表せる。グラフ理論は、こうしたものごとの関係を扱うのに役立つ。
このつながりの中を「探す」やり方が、これから見るBFS（幅優先探索）とDFS（深さ優先探索）だ。そして、最も短い道を求めるのがダイクストラ法だ。
詳しく：BFS・DFSとダイクストラ法
ここが心臓部。3つのアルゴリズムを表で押さえよう。
グラフの主なアルゴリズム
| 名前 | やさしい意味 |
|---|---|
| BFS（幅優先探索） | 近いところから、横に広げて順に探す |
| DFS（深さ優先探索） | 一本道を、できるだけ奥まで進んで探す |
| ダイクストラ法 | 重み（距離）つきのグラフで、最短経路を求める |
- BFS（幅優先探索） … 近い点から順に、横に広げて探すやり方。
- DFS（深さ優先探索） … 一本の道を、できるだけ奥まで進んでから戻るやり方。
ここで一番のポイント。最も短い道（最短経路）を求めるのは、ダイクストラ法だ。DFSは「深さ優先」なだけで、最短経路を保証しない。「DFSで最短経路が分かる」と思い込むと誤りになる。最短経路を知りたいときは、ダイクストラ法を使う。
わかりやすく言い換えると
身近なたとえで整理しよう。駅と路線の地図で考えるとわかりやすい。
グラフ理論は、「駅（点）と路線（線）のつながりを扱う考え方」のイメージ。SNSのつながりも、同じように表せる。
BFSとDFSは、「近い駅から順に調べる（BFS）」と「一本の路線を終点まで進む（DFS）」の違い。要するに、横に広げるか、奥に進むか、だ。
ダイクストラ法は、「いちばん短いルートを探す方法」。つまり、最短経路を知りたいときに使う、ということだ。
試験のツボ
🔴 一番出る：BFSとDFSの違い
①BFS（幅優先）＝近いところから横に広げて探す
②DFS（深さ優先）＝一本道を奥まで進んで探す
🔴 次に出る：最短経路はダイクストラ法
①最短経路を求めるのはダイクストラ法
②DFSは深さ優先なだけで、最短は保証しない
🟡 押さえると安定：グラフの正体と応用
①点（頂点）と線（辺）でつながりを表す
②SNS・交通網・Web検索などに使われる
よくある間違い
①「DFS（深さ優先探索）を使えば、最短経路が分かる」→ ✗ DFSは深さ優先なだけで、最短経路は保証しない。最短経路はダイクストラ法。
②「BFSとDFSは、まったく同じ探し方だ」→ ✗ BFSは横に広げて、DFSは奥に進んで探す。探し方が違う。
③「グラフ理論は、点だけ・線だけで成り立っている」→ ✗ グラフは、点（頂点）と線（辺）の両方でできている。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（グラフ理論の正体）
グラフ理論に関する次の記述のうち、最も適切なものはどれか。
- 社員の出退勤を記録して、毎月の給与を計算するためのしくみである
- 点（頂点）と線（辺）でできた、つながりを扱う数学のことである
- 取引先へ毎月の請求書を郵送する、決まった事務作業のことを指す
- 完成したシステムを宣伝して、より多く売るための広告活動である
解答は 2 だぱん。
グラフ理論は、点（頂点）と線（辺）でできたつながりを扱う数学なんだぱん。SNSや交通網など、関係を表すのに使うんだぱん。
選択肢1は給与計算、選択肢3は請求書の事務、選択肢4は広告で、どれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 給与計算のしくみではない |
| 2 | ✓ | 点と線のつながりを扱う数学で正しい |
| 3 | ✗ | 請求書の事務の話 |
| 4 | ✗ | 広告活動ではない |
オリジナル問題2（BFSとDFS）
BFSとDFSの違いに関する次の記述のうち、最も適切なものはどれか。
- BFSは奥まで進んで探し、DFSは横に広げて探すとされているものだ
- BFSもDFSも、社員の給与を計算するための方法だとされている
- BFSもDFSも、取引先へ請求書を郵送するための方法だとされる
- BFSは横に広げて探し、DFSは一本道を奥まで進んで探すものである
解答は 4 だぱん。
BFSは横に広げて探し、DFSは一本道を奥まで進んで探すものなんだぱん。横に広げるか、奥に進むか、の違いだぱん。
選択肢1は説明が逆、選択肢2は給与計算、選択肢3は請求書の事務で誤りだぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | BFSとDFSの説明が逆 |
| 2 | ✗ | 給与計算の方法ではない |
| 3 | ✗ | 請求書の事務の方法ではない |
| 4 | ✓ | BFSは横・DFSは奥で正しい |
オリジナル問題3（最短経路）
グラフで最短経路を求める方法として、最も適切なものはどれか。
- DFS（深さ優先探索）を使えば、必ず最短経路が分かるとされる
- 社員の給与を計算する方法で、最短経路を求めるとされているものだ
- ダイクストラ法で求める。DFSは最短経路を保証しないものである
- 取引先へ請求書を郵送する方法で、最短経路を求めるとされている
解答は 3 だぱん。
最短経路は、ダイクストラ法で求める。DFSは最短経路を保証しないんだぱん。DFSは深さ優先なだけだから、まちがえないようにするといいぱん。
選択肢1の「DFSで最短」、選択肢2の給与、選択肢4の請求書は、いずれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | DFSは最短を保証しない |
| 2 | ✗ | 給与計算の方法ではない |
| 3 | ✓ | ダイクストラ法で求めるで正しい |
| 4 | ✗ | 請求書の方法ではない |
まとめ
押さえどころ
- 🔴 グラフ理論 ＝ 点（頂点）と線（辺）でできたつながりを扱う数学。SNSや交通網に使う。
- 🔴 BFSとDFS ＝ BFS（幅優先）は横に広げて、DFS（深さ優先）は奥に進んで探す。
- 🟡 最短経路 ＝ ダイクストラ法で求める。DFSは深さ優先なだけで、最短は保証しない。
次に学ぶ
- 集合 ── ものの集まりを扱う考え方。グラフとあわせて、離散数学の基礎。
- アルゴリズム ── 問題を解く手順。BFS・DFS・ダイクストラ法も、その一種。
執筆: SikakuQuest編集部