循環参照があると探索が終わりません。グラフをBFSとDFSでたどり、訪問済みを持つ理由を確かめます。
これは【深掘り】の記事です。本線の順路ではありません。 このシリーズは言葉を覚える回にしません。 全部、手元で書いて、走らせて、出力を見ます。 飛ばしても本線は進めます。 本線側の関連記事は node_modulesは消してよい — npmとパッケージ管理 です。
この記事のコマンドは、VMの中(Ubuntu Server)で打ちます。 Windows の PowerShell ではありません。VM の立て方は VMを29台溜めた話 — Ubuntu Serverの立て方 にあります。
「グラフ理論」は、数学の人がやるものだと思っていました。
自分には関係ない、と。
そう思っていたころ、こういうコードを書いて、ターミナルを固めました。
// あるユーザーから辿れる人を全部集めたい
function collect(user) {
const result = [user];
for (const next of follows[user]) {
result.push(...collect(next)); // ← 再帰で辿る
}
return result;
}
戻ってきませんでした。
Ctrl+C も効かず、別のターミナルから pkill node して止めました。
原因は、いま書けば一行です。
「あきら → みなみ → かおる → あきら」という輪があった。
私はこのデータを「木」だと思っていました。 上から下に流れるものだと。 実際には輪になっていて、辿ると同じところに戻ってきます。戻ってきたら、また同じ道を辿ります。永遠に。
これがグラフです。 数式は一つも要りません。要るのは1つだけ。
一度行ったところを覚えておく。
そして気づきました。自分が毎日触っているものが、ほとんど全部グラフでした。 npm の依存関係も、Git のコミット履歴も、Docker Compose の depends_on も、路線図も、SNSのフォロー関係も。
この記事では、それを実際に画面に出して確かめてから、探索を2種類(幅優先と深さ優先)自分で書きます。
対象レベル: 中級〜上級 / 区分: 発展
この記事でわかること
- 木は「輪にならないグラフ」の一種にすぎない。 特別なものではない
- 輪があるから「訪問済み」の管理が要る。 これが木とグラフの決定的な違い
- 隣接リストと隣接行列の使い分けは「疎か密か」で決まること。頂点1000のグラフで実測する
- 有向(フォロー)と無向(友達)で、辿れる先が変わること
- 辺の重みが全部同じなら、BFS が最短経路を出す。 DFS では最短にならない
- 深いグラフでは、DFS の再帰版がスタックを溢れさせる。 ループ版なら通る
- 循環検出・トポロジカルソート・連結成分が、全部 DFS / BFS の応用でしかないこと
この記事でやること
- 実験用フォルダ
~/cslab/graphを作り、この記事の作業を全部そこに閉じ込める npm lsとgit log --graphを実際に打って、身の回りのグラフを目で見る- 隣接リストと隣接行列を両方実装し、メモリと問い合わせ速度を実測して表にする
- BFS をキューで、DFS をスタックと再帰の両方で書く
- 輪のあるグラフで
visitedを外し、止まらないことを安全に再現する - 最短経路・循環検出・トポロジカルソート・連結成分を、実際に動かして出力を見る
- 全域木を辺の一覧として出力し、頂点数 − 1 本になることを確かめる
先に知る言葉
この記事で初めて出てくる言葉です。 基本的な言葉は用語集にもまとめてあります。
| 言葉 | 意味 |
|---|---|
| グラフ | 点(頂点)と、それを繋ぐ線(辺)の集まり。それだけ |
| 頂点 / 辺 | 点が頂点、線が辺。英語では vertex / edge。v と e はこの頭文字 |
| 有向グラフ | 辺に向きがある。フォロー(片思いがありうる) |
| 無向グラフ | 辺に向きがない。友達(必ず両方向) |
| 次数 | その頂点から出ている辺の本数。有向なら出次数と入次数に分かれる |
| 隣接リスト | 各頂点の隣を配列で持つ。辺が少ないグラフに向く |
| 隣接行列 | n × n の表で持つ。「繋がっているか」が一発で分かるが場所を食う |
| 疎 / 密 | 辺が少ないのが疎、多いのが密。表し方の選択はここで決まる |
| サイクル(輪) | 辿っていくと元の頂点に戻ってくる道。これが無いグラフが「木」 |
| 連結成分 | 互いに辿り着ける頂点のかたまり。島と考えると早い |
① 準備 — 身の回りのグラフを見る
まず、自分が触っているものがグラフであることを確認します。 実験用のフォルダを作ります。最後に消します。
v22.14.0
node が無ければ、Node.js を入れる手順 を先に見てください。
npm の依存関係
パッケージを1つ入れて、依存を表示させます。
added 68 packages in 9s
express は1つしか入れていないのに、68個入りました。 中身を見ます。
npmdemo@1.0.0 /home/user/cslab/graph/npmdemo
`-- express@5.2.1
+-- accepts@2.0.0
| +-- mime-types@3.0.2 deduped
| `-- negotiator@1.1.0
| `-- content-type@2.1.0
+-- body-parser@2.3.0
| +-- bytes@3.1.2
| +-- content-type@2.1.0
| +-- debug@4.4.3 deduped
| +-- http-errors@2.0.1 deduped
| +-- iconv-lite@0.7.3
| | `-- safer-buffer@2.1.2
| +-- on-finished@2.4.1 deduped
| +-- qs@6.16.0 deduped
| +-- raw-body@3.0.2
| | +-- bytes@3.1.2 deduped
| | +-- http-errors@2.0.1 deduped
| | +-- iconv-lite@0.7.3 deduped
| | `-- unpipe@1.0.0
| `-- type-is@2.1.0 deduped
+-- content-disposition@1.1.0
+-- content-type@1.0.5
+-- cookie-signature@1.2.2
+-- cookie@0.7.2
+-- debug@4.4.3
| `-- ms@2.1.3
+-- depd@2.0.0
+-- encodeurl@2.0.0
+-- escape-html@1.0.3
npm ls は木の形で描いています。 けれど、よく見てください。
dedupedという札が何度も出てきます。
http-errors@2.0.1 deduped は、「これは木の別の場所に既に出ているので、ここでは省略した」という意味です。 つまり http-errors という1つの頂点に、複数の親から矢印が刺さっている。
木ならこうはなりません。木は親が1つだけだからです。
これはグラフです。
npm lsは、それを木の形に無理やり潰して表示しているだけです。
deduped の数を数えてみます。
43
43箇所で「もう出てきた」と言っています。 実体は 65 パッケージなのに、木として描くと 127 行になる。その差が、木とグラフの差です。
Git のコミット履歴
次は Git です。 練習用のリポジトリを作って、枝を分けて、合流させます。
そして履歴を図で出します。
* 1e93569 featureを取り込む
|\
| * 7b66a0b 機能を作る
* | 2c6a619 mainを直す
|/
* 811443b READMEを足す
* 3e9cccf 最初のコミット
|\ で枝が分かれ、|/ で合流しています。
マージコミット 1e93569 には、親が2つあります。 2c6a619 と 7b66a0b です。
「親が2つある」時点で、木ではありません。
Git のコミット履歴は、正確には DAG(有向非巡回グラフ) と呼ばれます。 向きがあって(子 → 親)、輪が無い。輪が無いのは、コミットは必ず「過去」を指すからです。
git log --graph の --graph は、比喩ではなく本当にグラフのことです。
Docker Compose の depends_on
depends_on も同じです。 サービスが頂点、依存が有向の辺です。
services:
web:
image: nginx
depends_on:
- api
api:
image: node
depends_on:
- db
- cache
cache:
image: redis
depends_on:
- web
db:
image: postgres
このファイルには輪が入っています。 web → api → cache → web。 目で見つけられますか。4サービスなら見つかります。20サービスあったら見つかりません。
⑦で、これを機械に見つけさせます。
Compose 自体の話は Composeなら1コマンド — 複数コンテナをまとめる にあります。
まとめると
| 身の回りのもの | 頂点 | 辺 | 向き | 輪 |
|---|---|---|---|---|
| npm の依存 | パッケージ | 依存 | あり | 稀にある(循環依存) |
| Git の履歴 | コミット | 親子 | あり | 無い(DAG) |
depends_on | サービス | 依存 | あり | 書けてしまう |
| 路線図 | 駅 | 線路 | 無い | ある(環状線) |
| SNSのフォロー | 人 | フォロー | あり | ある(相互フォロー) |
| フォルダ構造 | フォルダ | 親子 | あり | 無い = 木 |
一番下だけが木です。 木は特別なものではなく、「輪にならないグラフ」という条件付きのグラフでしかありません。 木そのものの話は 木にしたのに一直線になる — コンピュータ科学深掘り にあります。
輪がある。だから「もう行った」を覚えておく必要が出てくる。 木にはこの手間がありません。
スクリーンショットを撮ってください:
01_real_graphs.pngnpm ls --all | head -30とgit log --graph --oneline --allの出力が並んで写っているところ。dedupedの札と、|\の分岐が両方見えるように撮ってください。
② 表し方を2つ実装して比べる
グラフをプログラムに持たせる方法は、大きく2つです。
グラフ: A---B
| |
C---D
隣接リスト 隣接行列
A: [B, C] A B C D
B: [A, D] A [ 0 1 1 0 ]
C: [A, D] B [ 1 0 0 1 ]
D: [B, C] C [ 1 0 0 1 ]
D [ 0 1 1 0 ]
両方書きます。
// 隣接リスト: 各頂点の「隣」を配列で持つ
export class ListGraph {
constructor(n) {
this.n = n;
this.adj = Array.from({ length: n }, () => []);
}
addEdge(u, v) {
this.adj[u].push(v);
this.adj[v].push(u); // 無向なので両方に入れる
}
neighbors(u) { return this.adj[u]; }
hasEdge(u, v) { return this.adj[u].includes(v); } // O(次数)
}
// 隣接行列: n×n の表。m[u][v] が 1 なら辺がある
export class MatrixGraph {
constructor(n) {
this.n = n;
this.m = Array.from({ length: n }, () => new Uint8Array(n));
}
addEdge(u, v) {
this.m[u][v] = 1;
this.m[v][u] = 1;
}
neighbors(u) {
const out = [];
for (let v = 0; v < this.n; v++) if (this.m[u][v]) out.push(v); // O(n)
return out;
}
hasEdge(u, v) { return this.m[u][v] === 1; } // O(1)
}
neighbors と hasEdge で、得意・不得意が逆になっています。 ここが全部です。
メモリを実測する
頂点1000・辺5000のグラフで、両方のメモリを測ります。
import { ListGraph, MatrixGraph } from "./graph.mjs";
const N = 1000, E = 5000;
const edges = [];
for (let i = 0; i < E; i++) {
const u = Math.floor(Math.random() * N);
const v = Math.floor(Math.random() * N);
if (u !== v) edges.push([u, v]);
}
function measure(label, build) {
global.gc && global.gc();
const before = process.memoryUsage().heapUsed;
const g = build();
global.gc && global.gc();
const after = process.memoryUsage().heapUsed;
console.log(`${label}: ${((after - before) / 1024).toFixed(1)} KB`);
return g;
}
measure("隣接リスト", () => {
const g = new ListGraph(N);
for (const [u, v] of edges) g.addEdge(u, v);
return g;
});
measure("隣接行列 ", () => {
const g = new MatrixGraph(N);
for (const [u, v] of edges) g.addEdge(u, v);
return g;
});
console.log(`頂点 ${N} / 辺 ${edges.length}`);
console.log(`行列のマス数: ${(N * N).toLocaleString()}`);
console.log(`実際に埋まっているマス: ${(edges.length * 2).toLocaleString()}`);
console.log(`埋まっている割合: ${((edges.length * 2) / (N * N) * 100).toFixed(2)} %`);
隣接リスト: 107.6 KB
隣接行列 : 1017.4 KB
頂点 1000 / 辺 4996
行列のマス数: 1,000,000
実際に埋まっているマス: 9,992
埋まっている割合: 1.00 %
行列は 1,000,000 マス用意して、埋まっているのは 1% です。
| 表し方 | メモリ | マス数 | 使用率 |
|---|---|---|---|
| 隣接リスト | 107.6 KB | — | 辺の分だけ |
| 隣接行列 | 1017.4 KB | 1,000,000 | 1.00 % |
約9.5倍。 そしてこれは Uint8Array(1マス1バイト)を使った場合の数字です。 普通の配列(Array に数値を入れる)にすると、1マス8バイトになってさらに8倍になります。
頂点が10倍になると、行列のメモリは100倍になる。
n²だからです。 頂点10万の SNS を行列で持つと、100億マス。現実的ではありません。
「繋がっているか」の判定を実測する
では行列は要らないのか。 そうではありません。問い合わせの速さが逆転します。
import { ListGraph, MatrixGraph } from "./graph.mjs";
const N = 1000;
for (const E of [5000, 50000, 200000]) {
const list = new ListGraph(N), mat = new MatrixGraph(N);
for (let i = 0; i < E; i++) {
const u = Math.floor(Math.random() * N), v = Math.floor(Math.random() * N);
if (u === v) continue;
list.addEdge(u, v); mat.addEdge(u, v);
}
const Q = 100000, qs = [];
for (let i = 0; i < Q; i++) {
qs.push([Math.floor(Math.random() * N), Math.floor(Math.random() * N)]);
}
const bench = (fn) => {
const t = [];
for (let r = 0; r < 7; r++) {
const t0 = performance.now();
let h = 0;
for (const [u, v] of qs) if (fn(u, v)) h++;
t.push(performance.now() - t0);
}
t.sort((a, b) => a - b);
return t[3]; // 中央値
};
let deg = 0;
for (let u = 0; u < N; u++) deg += list.adj[u].length;
console.log(
`辺 ${String(E).padStart(6)} / 平均次数 ${(deg / N).toFixed(0).padStart(3)}` +
` | 行列 ${bench((u, v) => mat.hasEdge(u, v)).toFixed(2).padStart(7)} ms` +
` | リスト ${bench((u, v) => list.hasEdge(u, v)).toFixed(2).padStart(7)} ms`
);
}
辺 5000 / 平均次数 10 | 行列 11.62 ms | リスト 15.32 ms
辺 50000 / 平均次数 100 | 行列 17.24 ms | リスト 24.36 ms
辺 200000 / 平均次数 400 | 行列 11.23 ms | リスト 67.85 ms
行列は、辺を40倍にしても時間が変わっていません。 表を1マス見るだけだからです(O(1))。
リストは 15 → 68 ms と 4.4倍になりました。 includes が隣を順に舐めるからです(O(次数))。
| 操作 | 隣接リスト | 隣接行列 |
|---|---|---|
| メモリ | 辺の数に比例 | n² 固定 |
| 隣を全部並べる | O(次数) 速い | O(n) 遅い |
| AとBは繋がっているか | O(次数) | O(1) 速い |
| 辺を足す | O(1) | O(1) |
| 向いている形 | 疎(SNS・道路・依存関係) | 密(総当たり戦・距離表) |
迷ったら隣接リストです。 現実のグラフはほぼ全部「疎」だからです。 行列を選ぶのは、「頂点が少なくて、辺がぎっしり詰まっている」と分かっているときだけ。
計算量の記号そのものは データが10倍で100倍遅くなる — コンピュータ科学深掘り にあります。
以降は、名前で持てる隣接リスト(Map)を使います。
// この記事で使う無向グラフ(隣接リスト)
export const G = new Map(Object.entries({
A: ["B", "C"],
B: ["A", "D"],
C: ["A", "D", "G"],
D: ["B", "C", "E"],
E: ["D", "F"],
F: ["E"],
G: ["C", "H"],
H: ["G"],
}));
// 輪だけのグラフ。A と F は「直通」と「遠回り」の2通りで繋がっている
export const RING = new Map(Object.entries({
A: ["B", "F"],
B: ["A", "C"],
C: ["B", "D"],
D: ["C", "E"],
E: ["D", "F"],
F: ["E", "A"],
}));
図にするとこうです。
G(8頂点・8辺) RING(6頂点・6辺の輪)
A --- B
A --- B / \
| | F C
C --- D --- E --- F \ /
| E --- D
G --- H
③ 有向と無向 — 辿れる先が変わる
「フォロー」は有向です。 片思いがあります。 「友達」は無向です。 片方だけ友達、はありません。
同じデータから両方を作って、違いを出します。
const follows = [
["あきら", "みなみ"],
["みなみ", "かおる"],
["かおる", "あきら"],
["しおり", "あきら"],
["ゆう", "しおり"],
];
export function build(pairs, directed) {
const g = new Map();
const add = (a, b) => { g.get(a).push(b); };
for (const [a, b] of pairs) {
if (!g.has(a)) g.set(a, []);
if (!g.has(b)) g.set(b, []);
add(a, b);
if (!directed) add(b, a); // ← 無向なら逆向きも入れる
}
return g;
}
function show(title, g) {
console.log(`--- ${title} ---`);
for (const [k, v] of g) console.log(`${k} → ${v.length ? v.join(", ") : "(なし)"}`);
}
export const dir = build(follows, true);
export const und = build(follows, false);
show("有向(フォロー)", dir);
show("無向(友達)", und);
console.log("--- 次数 ---");
const inDeg = new Map([...dir.keys()].map((k) => [k, 0]));
for (const [, vs] of dir) for (const v of vs) inDeg.set(v, inDeg.get(v) + 1);
for (const k of dir.keys()) {
console.log(`${k}: 出次数 ${dir.get(k).length} / 入次数 ${inDeg.get(k)}`);
}
--- 有向(フォロー) ---
あきら → みなみ
みなみ → かおる
かおる → あきら
しおり → あきら
ゆう → しおり
--- 無向(友達) ---
あきら → みなみ, かおる, しおり
みなみ → あきら, かおる
かおる → みなみ, あきら
しおり → あきら, ゆう
ゆう → しおり
--- 次数 ---
あきら: 出次数 1 / 入次数 2
みなみ: 出次数 1 / 入次数 1
かおる: 出次数 1 / 入次数 1
しおり: 出次数 1 / 入次数 1
ゆう: 出次数 1 / 入次数 0
同じ5本の関係が、無向にすると隣が倍に増えています。
入次数と出次数の意味も、これで一発で分かります。
| 意味 | SNSで言うと | |
|---|---|---|
| 出次数 | そこから出ている辺 | フォローしている数 |
| 入次数 | そこに入ってくる辺 | フォロワー数 |
「ゆう」の入次数は 0 です。 誰にもフォローされていない。 無向グラフには、この区別がありません。 辺は必ず両方向だからです。
そして、辿れる先が変わります。 ④で作る BFS を先に使って見せます。
// direction.mjs の末尾に足す
import { bfs } from "./search.mjs";
console.log("--- ゆう から辿れる人 ---");
console.log("有向:", bfs(dir, "ゆう").order.join(" → "));
console.log("無向:", bfs(und, "ゆう").order.join(" → "));
console.log("--- かおる から辿れる人 ---");
console.log("有向:", bfs(dir, "かおる").order.join(" → "));
console.log("無向:", bfs(und, "かおる").order.join(" → "));
--- ゆう から辿れる人 ---
有向: ゆう → しおり → あきら → みなみ → かおる
無向: ゆう → しおり → あきら → みなみ → かおる
--- かおる から辿れる人 ---
有向: かおる → あきら → みなみ
無向: かおる → みなみ → あきら → しおり → ゆう
「かおる」から辿れる人が、有向では3人、無向では5人です。
同じデータ、同じ探索コード。違うのは辺の向きだけ。
「向きを入れるか入れないか」は、後から直しにくい設計判断です。 フォロー機能を作るとき、ここを間違えると「片思いが表現できない」データベースができます。
④ 幅優先探索(BFS)— 近いところから波紋のように
BFS は、キューを使います。 前の回で作ったものです(call stack size exceeded の正体)。
動き方は「波紋」です。
A から BFS を始めると
距離0: A
距離1: B C ← A の隣を全部
距離2: D G ← B と C の隣を全部
距離3: E H
距離4: F
書きます。
// 前の回で作ったキュー(先頭を shift しない=O(1))
export class Queue {
constructor() { this.buf = []; this.head = 0; }
push(x) { this.buf.push(x); }
shift() { return this.buf[this.head++]; }
get size() { return this.buf.length - this.head; }
}
// 幅優先探索: キューを使う。近いところから広がる
export function bfs(g, start) {
const dist = new Map([[start, 0]]);
const prev = new Map([[start, null]]);
const order = [];
const q = new Queue();
q.push(start);
while (q.size > 0) {
const u = q.shift();
order.push(u);
for (const v of g.get(u)) {
if (dist.has(v)) continue; // ← 訪問済みなら二度と入れない
dist.set(v, dist.get(u) + 1); // 距離は「来た頂点 + 1」
prev.set(v, u); // どこから来たかを覚える
q.push(v);
}
}
return { order, dist, prev };
}
// prev をたどって経路を復元する
export function pathTo(prev, goal) {
const path = [];
let cur = goal;
while (cur !== undefined && cur !== null) { path.push(cur); cur = prev.get(cur); }
return path.reverse();
}
dist が「訪問済み」の役目も兼ねています。 dist.has(v) が真なら、もう見た頂点です。
走らせます。
import { G } from "./sample.mjs";
import { bfs, pathTo } from "./search.mjs";
const { order, dist, prev } = bfs(G, "A");
console.log("訪問順:", order.join(" → "));
console.log("--- Aからの距離(何ホップか) ---");
for (const [k, d] of [...dist].sort((a, b) => a[1] - b[1] || (a[0] < b[0] ? -1 : 1))) {
console.log(`${k}: ${d}`);
}
console.log("AからFへの経路:", pathTo(prev, "F").join(" → "));
console.log("AからHへの経路:", pathTo(prev, "H").join(" → "));
訪問順: A → B → C → D → G → E → H → F
--- Aからの距離(何ホップか) ---
A: 0
B: 1
C: 1
D: 2
G: 2
E: 3
H: 3
F: 4
AからFへの経路: A → B → D → E → F
AからHへの経路: A → C → G → H
距離が 0, 1, 1, 2, 2, 3, 3, 4 と、きれいに階段になっています。
これは偶然ではありません。 キューは先に入れたものが先に出るので、 距離1の頂点を全部処理してからでないと、距離2の頂点に手を付けないからです。
辺の重みが全部同じなら(=「1本は1本」なら)、BFS が出す経路が最短経路です。
なぜ最短だと言い切れるのか。
prev に書き込むのは、その頂点を「初めて見たとき」1回だけです。 そして初めて見るのは、一番近い距離から順に広げているから、必ず最短の道から来たときです。 あとから別の道で同じ頂点に着いても、dist.has(v) で弾かれて prev は上書きされません。
A → F の距離が 4 であることは、目でも確かめられます。 A-B-D-E-F で4本。他に短い道はありません。
⑤ 深さ優先探索(DFS)— 行けるところまで行って戻る
DFS はスタックを使います。 あるいは再帰です。再帰は、言語が用意したスタックを借りているだけです。
A から DFS を始めると
A → B → D → C → G → H (行き止まり、戻る)
→ E → F (C の隣は尽きたので D に戻って E へ)
両方書きます。
// search.mjs に足す
// 深さ優先探索(再帰版)
export function dfsRecursive(g, start) {
const visited = new Set();
const order = [];
const prev = new Map([[start, null]]);
function go(u) {
visited.add(u);
order.push(u);
for (const v of g.get(u)) {
if (visited.has(v)) continue;
prev.set(v, u);
go(v); // ← ここで一段潜る
}
}
go(start);
return { order, prev };
}
// 深さ優先探索(ループ版): 自分でスタックを持つ
export function dfsLoop(g, start) {
const visited = new Set();
const order = [];
const prev = new Map([[start, null]]);
const stack = [start];
while (stack.length > 0) {
const u = stack.pop(); // ← push / pop なのでスタック
if (visited.has(u)) continue; // ⚠️ 取り出したときにも確認する
visited.add(u);
order.push(u);
const ns = g.get(u);
for (let i = ns.length - 1; i >= 0; i--) { // 再帰版と同じ順に見せるため逆から
const v = ns[i];
if (visited.has(v)) continue;
if (!prev.has(v)) prev.set(v, u);
stack.push(v);
}
}
return { order, prev };
}
ループ版では、stack.pop() した直後にも visited を確認しています。 スタックには同じ頂点が複数入りうる(別の頂点から2回積まれる)ので、入れる時のチェックだけでは足りません。
BFS と並べます。
import { G, RING } from "./sample.mjs";
import { bfs, dfsRecursive, dfsLoop, pathTo } from "./search.mjs";
const b = bfs(G, "A");
const dr = dfsRecursive(G, "A");
const dl = dfsLoop(G, "A");
console.log("BFS 訪問順:", b.order.join(" → "));
console.log("DFS 再帰 訪問順:", dr.order.join(" → "));
console.log("DFS ループ訪問順:", dl.order.join(" → "));
console.log("再帰版とループ版は同じか:", dr.order.join() === dl.order.join());
console.log("--- 輪のグラフで A から F へ ---");
const pb = pathTo(bfs(RING, "A").prev, "F");
const pd = pathTo(dfsRecursive(RING, "A").prev, "F");
console.log(`BFS: ${pb.join(" → ")} (辺 ${pb.length - 1} 本)`);
console.log(`DFS: ${pd.join(" → ")} (辺 ${pd.length - 1} 本)`);
BFS 訪問順: A → B → C → D → G → E → H → F
DFS 再帰 訪問順: A → B → D → C → G → H → E → F
DFS ループ訪問順: A → B → D → C → G → H → E → F
再帰版とループ版は同じか: true
--- 輪のグラフで A から F へ ---
BFS: A → F (辺 1 本)
DFS: A → B → C → D → E → F (辺 5 本)
同じグラフ・同じ出発点で、A → F が BFS では1本、DFS では5本です。
RING グラフでは、A と F は直接繋がっています。 BFS は距離1で見つけます。 DFS は A の隣リストの先頭が B なので、そちらに突っ込んで、輪をぐるっと回って裏から F に着きます。
DFS は「見つける」けれど、「最短で見つける」とは限りません。 経路の長さを気にするなら BFS。気にしないなら DFS。 ここが最初の分かれ道です。
深いグラフで再帰版が落ちる
一直線のグラフを作って、両方に流します。
import { dfsRecursive, dfsLoop } from "./search.mjs";
// 一直線のグラフ: 0 - 1 - 2 - ... - (N-1)
function chain(n) {
const g = new Map();
for (let i = 0; i < n; i++) {
const ns = [];
if (i > 0) ns.push(String(i - 1));
if (i < n - 1) ns.push(String(i + 1));
g.set(String(i), ns);
}
return g;
}
for (const n of [1000, 50000]) {
const g = chain(n);
try {
const r = dfsRecursive(g, "0");
console.log(`N=${n} 再帰版: 訪問 ${r.order.length} 頂点`);
} catch (e) {
console.log(`N=${n} 再帰版: ${e.constructor.name}: ${e.message}`);
}
const r2 = dfsLoop(g, "0");
console.log(`N=${n} ループ版: 訪問 ${r2.order.length} 頂点`);
}
N=1000 再帰版: 訪問 1000 頂点
N=1000 ループ版: 訪問 1000 頂点
N=50000 再帰版: RangeError: Maximum call stack size exceeded
N=50000 ループ版: 訪問 50000 頂点
1000頂点なら通り、50000頂点で落ちました。 ループ版は通ります。
これが厄介なのは、「手元のテストデータでは通ってしまう」ところです。 私は8頂点のテストしか書いていませんでした。本番のデータが深かったら、そこで初めて落ちます。
| 再帰版 | ループ版 | |
|---|---|---|
| 読みやすさ | こちらが読みやすい | スタック操作が見える分うるさい |
| 深さの上限 | 言語のスタック(数万段で落ちる) | ヒープ。実質メモリまで |
| 帰りがけの処理 | 書きやすい(⑦のトポロジカルソート) | 一工夫要る |
書くときは再帰、深さが読めないデータに使うときはループ版。 「深さが読めない」の代表が、ユーザーが作るデータです。 フォルダの入れ子、返信の連鎖、組織の階層。
エラーの正体そのものは call stack size exceeded の正体 — コンピュータ科学深掘り にあります。
スクリーンショットを撮ってください:
02_bfs_dfs_order.pngnode compare.mjsの出力全体。 BFS と DFS の訪問順が並び、A → Fが「1本」と「5本」になっているところが写るように撮ってください。
⑥ 訪問済みを忘れると止まらない
ここがこの記事の中心です。
導入で書いたとおり、私はこれで pkill node しました。同じことを、安全に再現します。
本当に無限ループさせると、ターミナルが固まって記事どころではありません。 回数の上限を付けて、超えたら例外にします。
import { RING } from "./sample.mjs";
// ⚠️ わざと visited を外した BFS。回数の上限を付けて固まらないようにする
function bfsNoVisited(g, start, limit = 30) {
const order = [];
const queue = [start];
let steps = 0;
while (queue.length > 0) {
if (++steps > limit) {
throw new Error(`${limit} 回を超えました。まだ ${queue.length} 個キューに残っています`);
}
const u = queue.shift();
order.push(u);
for (const v of g.get(u)) queue.push(v); // ← 訪問済みかどうかを見ていない
}
return order;
}
try {
console.log(bfsNoVisited(RING, "A").join(" → "));
} catch (e) {
console.log("止めました:", e.message);
}
// visited を入れた版
function bfsSafe(g, start, limit = 30) {
const visited = new Set([start]);
const order = [];
const queue = [start];
let steps = 0;
while (queue.length > 0) {
if (++steps > limit) throw new Error("上限を超えました");
const u = queue.shift();
order.push(u);
for (const v of g.get(u)) {
if (visited.has(v)) continue;
visited.add(v);
queue.push(v);
}
}
return order;
}
console.log("visited あり:", bfsSafe(RING, "A").join(" → "));
// 木(輪が無い)なら、visited が無くても止まる
const TREE = new Map(Object.entries({
root: ["a", "b"], a: ["c", "d"], b: ["e"], c: [], d: [], e: [],
}));
console.log("木で visited なし:", bfsNoVisited(TREE, "root").join(" → "));
止めました: 30 回を超えました。まだ 31 個キューに残っています
visited あり: A → B → F → C → E → D
木で visited なし: root → a → b → c → d → e
30回処理したのに、キューには31個残っています。
取り出すたびに、それ以上入れている。 キューは縮むどころか育ち続けます。 上限を外していたら、メモリを食い尽くすまで止まりません。
そして3行目。
同じコード(
visitedなし)を木に流すと、ちゃんと止まりました。
これが木とグラフの決定的な違いです。
| 木 | グラフ | |
|---|---|---|
| 輪 | 無い | ある |
| 親 | 1つ | いくつでも |
visited | 無くても止まる | 無いと止まらない |
| 同じ頂点に2回着くか | 着かない | 着く |
私が最初に書いたコードは、木のつもりで書いた探索でした。 データがグラフだっただけです。
グラフを辿るコードを書くときは、
visitedを1行目に書く。 後から足すのではなく、最初に書く。
上限を付ける癖は、そのまま残す
この「上限を付けて例外にする」やり方は、実験用の飾りではありません。
if (++steps > limit) throw new Error("上限を超えました");
この2行が入っていれば、visited を書き忘れても、固まらずに例外で教えてくれます。
ターミナルが固まると、原因を見る手段そのものが失われます。 例外なら、スタックトレースが出て、どこで起きたか分かります。
私は前の回で二分探索の無限ループをやってから、探索のループには必ず上限を入れることにしました。 1回引くだけなら並べると損 — コンピュータ科学深掘り に同じ話があります。
⑦ BFS と DFS の使い分けを、実際の問題で
ここまでで道具は揃いました。 実際の問題に当てます。
1. 最短経路(重みなし)→ BFS
⑤で見たとおりです。 同じグラフで BFS は1本、DFS は5本でした。
「最短」が要るなら BFS 一択。DFS で最短を出すには、全部の経路を試すことになります。
逆に、辺に「重み」(距離・時間・料金)が付くと、BFS では最短になりません。 そこは次の回の話です。
2. 循環の検出 → DFS
①で作った compose.yml の輪を、機械に見つけさせます。
DFS で頂点を3色に塗り分けます。
白 = まだ行っていない
灰 = いま辿っている道の上にいる ← ここに戻ったら輪
黒 = 辿り終わった
「灰の頂点に着いた」=「いま来た道を遡ると自分に戻れる」= 輪です。 黒はダメです。 黒は「別の道からも行ける」だけで、輪ではありません。
// depends_on のような有向グラフ。「A: [B]」は「A は B に依存する」
export const DEPS = new Map(Object.entries({
web: ["api"],
api: ["db", "cache"],
worker: ["db", "queue"],
db: [],
cache: [],
queue: [],
}));
// ⚠️ わざと輪を作った版: cache が web に依存している
export const CYCLIC = new Map(Object.entries({
web: ["api"],
api: ["db", "cache"],
cache: ["web"],
worker: ["db", "queue"],
db: [],
queue: [],
}));
// DFS で輪を探す。白=未訪問 / 灰=いま辿っている途中 / 黒=終わった
export function findCycle(g) {
const color = new Map([...g.keys()].map((k) => [k, "白"]));
const stack = [];
let found = null;
function go(u) {
color.set(u, "灰");
stack.push(u);
for (const v of g.get(u)) {
if (color.get(v) === "灰") { // ← いま辿っている道の上に戻った=輪
found = [...stack.slice(stack.indexOf(v)), v];
return true;
}
if (color.get(v) === "白" && go(v)) return true;
}
stack.pop();
color.set(u, "黒");
return false;
}
for (const u of g.keys()) if (color.get(u) === "白" && go(u)) break;
return found;
}
// トポロジカルソート: DFS の「帰りがけ」に積む
export function topoSort(g) {
const cycle = findCycle(g);
if (cycle) throw new Error(`輪があるので順番を決められません: ${cycle.join(" → ")}`);
const visited = new Set();
const out = [];
function go(u) {
visited.add(u);
for (const v of g.get(u)) if (!visited.has(v)) go(v);
out.push(u); // ← 依存先を全部終えてから自分を積む
}
for (const u of g.keys()) if (!visited.has(u)) go(u);
return out; // 依存先が先に来る=起動してよい順
}
import { DEPS, CYCLIC, findCycle, topoSort } from "./deps.mjs";
console.log("--- 輪があるか ---");
console.log("DEPS :", findCycle(DEPS) ?? "輪なし");
console.log("CYCLIC:", (findCycle(CYCLIC) ?? []).join(" → "));
console.log("--- 起動してよい順(トポロジカルソート) ---");
console.log(topoSort(DEPS).join(" → "));
console.log("--- 輪があるグラフでやると ---");
try {
topoSort(CYCLIC);
} catch (e) {
console.log(e.message);
}
--- 輪があるか ---
DEPS : 輪なし
CYCLIC: web → api → cache → web
--- 起動してよい順(トポロジカルソート) ---
db → cache → api → web → queue → worker
--- 輪があるグラフでやると ---
輪があるので順番を決められません: web → api → cache → web
web → api → cache → web と、輪の中身をそのまま出せました。
「輪がある」だけでは直せません。 どの辺を切ればいいかが分かるように、輪の頂点を並べて返すのが大事です。
3. 本物の compose.yml から検出する
手で書き写すのではなく、ファイルから読みます。
import { readFileSync } from "node:fs";
import { findCycle } from "./deps.mjs";
// compose.yml から services と depends_on だけを拾う(この形だけを想定した簡易版)
const lines = readFileSync("compose.yml", "utf8").split("\n");
const g = new Map();
let service = null, inDeps = false;
for (const line of lines) {
const svc = line.match(/^ ([\w-]+):$/);
if (svc) { service = svc[1]; g.set(service, []); inDeps = false; continue; }
if (/^ depends_on:$/.test(line)) { inDeps = true; continue; }
const dep = line.match(/^ - ([\w-]+)$/);
if (inDeps && dep) { g.get(service).push(dep[1]); continue; }
if (/^ \w/.test(line)) inDeps = false;
}
for (const [k, v] of g) console.log(`${k} → ${v.length ? v.join(", ") : "(依存なし)"}`);
const cycle = findCycle(g);
console.log(cycle ? `⚠️ 輪があります: ${cycle.join(" → ")}` : "輪なし");
web → api
api → db, cache
cache → web
db → (依存なし)
⚠️ 輪があります: web → api → cache → web
①で目視した輪を、機械が見つけました。
この簡易パーサは、この形の YAML しか読めません。 それでいいです。 大事なのは「設定ファイルはグラフとして読める」という一点です。
同じ理屈が使えるもの:
| 場面 | 何がグラフか | 輪があると |
|---|---|---|
| Docker Compose | サービスと depends_on | 起動順が決められない |
| npm の依存 | パッケージと依存 | 循環依存。ビルドやバンドルで問題になる |
| DBのマイグレーション | マイグレーションと前提 | 適用順が決まらない |
| ビルド(Make など) | 成果物と入力 | 無限に作り直す |
| モジュールの import | ファイルと import | 片方が undefined で読み込まれる |
4. トポロジカルソートの中身
出力をもう一度見ます。
db → cache → api → web → queue → worker
db が最初、web が api より後。 依存先が必ず先に来ています。
なぜ「帰りがけに積む」だけでこうなるのか。
function go(u) {
visited.add(u);
for (const v of g.get(u)) if (!visited.has(v)) go(v);
out.push(u); // ← ここ。子を全部やり終えてから
}
out.push(u) は、u の依存先を全部処理し終えた後に実行されます。 だから out の中では、必ず依存先のほうが先に入っている。それだけです。
順番を1行も書いていないのに、正しい起動順が出ました。
depends_onを書けば Compose が順番を決めてくれるのは、内部でこれをやっているからです。
5. 連結成分(島がいくつあるか)
「全員に届くか」を調べるのが連結成分です。
import { bfs } from "./search.mjs";
// 3つの島があるグラフ
const NET = new Map(Object.entries({
A: ["B", "C"], B: ["A"], C: ["A"],
D: ["E"], E: ["D"],
F: [],
}));
function components(g) {
const seen = new Set();
const groups = [];
for (const u of g.keys()) {
if (seen.has(u)) continue;
const { order } = bfs(g, u); // まだ見ていない頂点から探索を始める
for (const v of order) seen.add(v);
groups.push(order);
}
return groups;
}
const gs = components(NET);
console.log(`島の数: ${gs.length}`);
gs.forEach((g, i) => console.log(`島${i + 1}: ${g.join(", ")} (${g.length}頂点)`));
島の数: 3
島1: A, B, C (3頂点)
島2: D, E (2頂点)
島3: F (1頂点)
「まだ見ていない頂点があれば、そこから新しい探索を始める」だけです。
BFS でも DFS でも同じ結果になります。 順番が違うだけで、島の分け方は変わりません。
実務でどこに出るか:
| 場面 | 島が2つ以上あると |
|---|---|
| ネットワークの疎通 | 届かないセグメントがある |
| SNSの友達関係 | 孤立したグループがいる |
| 依存グラフ | 使われていないモジュールの塊が見つかる |
| クラスタのノード | スプリットブレイン(両側が「自分が正しい」と思う) |
使い分けの表
| やりたいこと | 使う | 理由 |
|---|---|---|
| 最短経路(重みなし) | BFS | 近い順に広げるから、初めて着いたときが最短 |
| とにかく全部辿る | どちらでも | 訪問順が違うだけ |
| 循環の検出 | DFS | 「いま辿っている道」が分かるのは DFS だけ |
| トポロジカルソート | DFS | 帰りがけに積むだけで順序になる |
| 連結成分 | どちらでも | 未訪問から始め直すだけ |
| 深さが読めないデータ | BFS かループ版 DFS | 再帰版はスタックが溢れる |
| メモリが厳しい | DFS | BFS は「その距離の頂点全部」をキューに載せる |
最後の行は見落としやすい点です。 BFS は横に広いグラフで、キューが一気に膨らみます。 SNS のように「1人が1万人フォロー」だと、距離1の時点で1万件です。
スクリーンショットを撮ってください:
03_cycle_topo.pngnode run-deps.mjsとnode read-compose.mjsの出力。web → api → cache → webの輪と、db → cache → api → webの起動順が両方見えるように撮ってください。
⑧ 全域木 — 探索した跡が、そのまま木になる
全域木とは、「すべての頂点を、輪を作らずに繋ぐ辺の集まり」です。
そして、これは新しく作るものではありません。 BFS や DFS を1回回せば、勝手にできています。 prev(どこから来たか)がそれです。
import { G } from "./sample.mjs";
import { bfs, dfsRecursive } from "./search.mjs";
// prev(どこから来たか)を辺の集まりに直すと、それが全域木
function treeEdges(prev) {
const edges = [];
for (const [v, u] of prev) if (u !== null) edges.push(`${u}-${v}`);
return edges;
}
function countEdges(g) {
let c = 0;
for (const [, ns] of g) c += ns.length;
return c / 2; // 無向なので2回数えている
}
const b = treeEdges(bfs(G, "A").prev);
const d = treeEdges(dfsRecursive(G, "A").prev);
console.log(`元のグラフ: 頂点 ${G.size} / 辺 ${countEdges(G)}`);
console.log(`BFS の全域木 (${b.length} 本):`, b.join(" "));
console.log(`DFS の全域木 (${d.length} 本):`, d.join(" "));
console.log(`頂点 ${G.size} を輪なしで繋ぐのに要る辺: ${G.size - 1} 本`);
元のグラフ: 頂点 8 / 辺 8
BFS の全域木 (7 本): A-B A-C B-D C-G D-E G-H E-F
DFS の全域木 (7 本): A-B B-D D-C C-G G-H D-E E-F
頂点 8 を輪なしで繋ぐのに要る辺: 7 本
元のグラフは辺が8本。全域木はどちらも7本です。
8頂点を輪なしで繋ぐには、必ず7本要ります。 そして7本を超えると、必ずどこかに輪ができます。
頂点 n を輪なしで繋ぐ辺は、必ず n − 1 本。 これは木の定義そのものです。
BFS と DFS で、選ばれた辺が違います。
元のグラフ BFSの全域木 DFSの全域木
A --- B A --- B A --- B
| | | | |
C --- D --- E C D --- E C --- D --- E
| | | | |
G --- H G --- H F G --- H F
BFS の木は「浅く広い」、DFS の木は「細く深い」形になります。
元のグラフには C-D と B-D の両方がありました。 BFS は B-D を、DFS は D-C を選んでいます。 どちらも正しい全域木です。
「1つに決まらない」のが全域木です。 出発点や隣の並び順で変わります。
実務でどこに出るか
| 場面 | 全域木の役割 |
|---|---|
| スイッチのループ防止 | 輪があるとパケットが永遠に回るので、木にして一部の線を止める |
| 配線・配管の設計 | すべてを繋ぐ最小の線の引き方 |
| クラスタリング | 木を作って、長い辺を切ると自然に分かれる |
そして、ここに1つ足りないものがあります。
この記事のグラフには「重み」がありません。 辺はどれも「1本」でした。 現実の路線図には距離があり、ネットワークには遅延があり、道路には料金があります。
重みが入った瞬間、この記事のやり方は全部通じなくなります。
- BFS は最短経路を出さなくなる(辺の本数が少なくても、合計距離が長いかもしれない)
- 全域木も「どれでもいい」ではなくなる(合計の重みを一番小さくしたい = 最小全域木)
次の回で、そこをやります。 ここまでのコードは、そのまま土台になります。
つまずいたところ
データを木だと思い込んでいた。 これが導入の失敗の全部です。「上から下に流れる」という思い込みで、visited を書きませんでした。輪があるかどうかは、コードを見ても分かりません。データを見ないと分かりません。 そしてユーザーが作るデータには、必ず輪が入ります(相互フォロー、循環参照)。
無限ループでターミナルが固まって、原因が見られなかった。 Ctrl+C が効かず pkill node しました。固まるとログもスタックトレースも見られません。 それ以来、探索のループには必ず回数の上限を入れて、超えたら例外にしています。⑥のコードがそれです。例外なら、どこで起きたかが出ます。
DFS のループ版で、push するときだけ visited を確認していた。 同じ頂点が別の頂点から2回スタックに積まれるので、2回訪問されて order が重複しました。pop() した直後にも visited.has(u) を確認する必要があります。再帰版にはこの問題がありません(積む場所が1箇所しかないため)。
8頂点のテストしか書かず、再帰版の DFS を本番に出しかけた。 1000頂点では通り、50000頂点で RangeError です。 手元のテストデータで通ることは、深さの安全を1ミリも保証しません。深さが読めないデータには、必ずループ版か BFS を使うと決めました。
循環検出で「訪問済み」だけを見ていた。 「もう見た頂点に着いた=輪」だと思って書いたら、輪が無いグラフでも輪があると言われました。必要なのは「訪問済みか」ではなく「いま辿っている道の上にいるか」です。3色(白・灰・黒)に分けたら一発で直りました。黒(辿り終わった)に着くのは、単に合流しただけです。
トポロジカルソートで out.push(u) を関数の先頭に書いた。 逆順(依存元が先)が出てきて、web が db より前に来ました。「行きがけ」ではなく「帰りがけ」に積む。 1行の位置で結果が真逆になります。
隣接行列を普通の Array で作って、メモリが8倍になった。 頂点1000で 8MB です。Uint8Array にしたら 1MB になりました。 ただし根本の問題は n² のほうで、頂点を10万にしたらどちらでも足りません。そもそも疎なグラフに行列を使ったのが間違いでした。
npm ls の deduped を、ずっと「重複だから消した」だと読んでいた。 正しくは「木の別の場所に既に出ているので、ここでは省略した」です。同じパッケージに複数の親から矢印が刺さっているという、グラフであることの印でした。表示が木の形なので、木だと思い込んでいました。
後片づけ
実験用フォルダを消します。 node_modules も入っているので、まとめて消えます。
graph が消えていれば完了です。
gitdemo の中で git を試した人は、リポジトリごと消えています。 消したくないものを ~/cslab/graph の中に置いていないか、消す前に確認してください。
まとめ — 理解できたこと
- グラフは「点と、それを繋ぐ線」だけ。 数式は要らない
- 木はグラフの一種にすぎない。 「輪にならない」という条件が付いただけ
- npm の依存も、Git の履歴も、
depends_onも、路線図も、フォロー関係も全部グラフ npm lsのdedupedは、木として描けなかった印。 実体はグラフgit log --graphの--graphは比喩ではない。 マージコミットは親が2つ = 木ではない- 表し方は「疎か密か」で決める。 頂点1000・辺5000で、隣接リスト 108KB vs 隣接行列 1017KB(9.5倍、埋まっているのは1%)
- 「繋がっているか」の判定は行列が
O(1)。 辺を40倍にしても 11ms のまま。リストは 15 → 68ms - 迷ったら隣接リスト。 現実のグラフはほぼ全部「疎」
- 有向と無向で、辿れる先が変わる。 同じデータで「かおる」から辿れるのが3人 vs 5人
- BFS はキュー、DFS はスタック(または再帰)。 それだけの違いで性格が変わる
- 辺の重みが全部同じなら、BFS が最短経路を出す。 初めて着いたときが最短だから
- DFS は最短にならない。 同じグラフで
A → Fが BFS 1本、DFS 5本 - 深いグラフで再帰版の DFS は落ちる。 1000頂点は通り、50000頂点で
RangeError - 一番大事: 輪があるグラフで
visitedを外すと止まらない。 30回処理してキューに31個残った - 同じコードを木に流すと、
visitedが無くても止まる。 これが木とグラフの決定的な違い - 循環検出は3色(白・灰・黒)。 「訪問済み」ではなく「いま辿っている道の上か」を見る
- トポロジカルソートは DFS の帰りがけに積むだけ。 順番を1行も書かずに起動順が出る
- 全域木は作るものではなく、探索した跡。 頂点 n なら必ず n − 1 本
参考リンク
- roadmap.sh — Computer Science
- MDN — Map
- MDN — Set
- MDN — Uint8Array
- Node.js — process.memoryUsage
- Node.js — Performance measurement APIs
- Git — git-log のドキュメント
- npm — npm ls のドキュメント
- Docker — Compose の depends_on
次に読む
この記事は 【深掘り】コンピュータ科学 の 13 / 25 本目です。
| 記事 | |
|---|---|
| ← 前の記事 | 線形探索と二分探索 — 1回引くだけなら並べると損 |
| → 次の記事 | 最短経路アルゴリズム — ダイクストラは負の重みで壊れる |
上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。
全体の順路は はじめに にあります。
roadmap.sh のどこをやっているか
- 隣接リストと隣接行列を実測で選ぶ
- 訪問済みを忘れると止まらない
この記事は、上の項目を実際に手を動かして確かめる回です。

コメント