グラフとBFS・DFS — 循環参照で探索が止まらない

グラフとBFS・DFS。輪を含む点と線のネットワーク模型と訪問済みのチェックマーク。

循環参照があると探索が終わりません。グラフをBFSとDFSでたどり、訪問済みを持つ理由を確かめます。

前回: 線形探索と二分探索 — 1回引くだけなら並べると損

これは【深掘り】の記事です。本線の順路ではありません。 このシリーズは言葉を覚える回にしません。 全部、手元で書いて、走らせて、出力を見ます。 飛ばしても本線は進めます。 本線側の関連記事は 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 の応用でしかないこと

この記事でやること

  1. 実験用フォルダ ~/cslab/graph を作り、この記事の作業を全部そこに閉じ込める
  2. npm ls と git log --graph を実際に打って、身の回りのグラフを目で見る
  3. 隣接リストと隣接行列を両方実装し、メモリと問い合わせ速度を実測して表にする
  4. BFS をキューで、DFS をスタックと再帰の両方で書く
  5. 輪のあるグラフで visited を外し、止まらないことを安全に再現する
  6. 最短経路・循環検出・トポロジカルソート・連結成分を、実際に動かして出力を見る
  7. 全域木を辺の一覧として出力し、頂点数 − 1 本になることを確かめる

先に知る言葉

この記事で初めて出てくる言葉です。 基本的な言葉は用語集にもまとめてあります。

言葉意味
グラフ点(頂点)と、それを繋ぐ線(辺)の集まり。それだけ
頂点 / 辺点が頂点、線が辺。英語では vertex / edge。v と e はこの頭文字
有向グラフ辺に向きがある。フォロー(片思いがありうる)
無向グラフ辺に向きがない。友達(必ず両方向)
次数その頂点から出ている辺の本数。有向なら出次数と入次数に分かれる
隣接リスト各頂点の隣を配列で持つ。辺が少ないグラフに向く
隣接行列n × n の表で持つ。「繋がっているか」が一発で分かるが場所を食う
疎 / 密辺が少ないのが疎、多いのが密。表し方の選択はここで決まる
サイクル(輪)辿っていくと元の頂点に戻ってくる道。これが無いグラフが「木」
連結成分互いに辿り着ける頂点のかたまり。島と考えると早い

① 準備 — 身の回りのグラフを見る

まず、自分が触っているものがグラフであることを確認します。 実験用のフォルダを作ります。最後に消します。

bash
$ mkdir -p ~/cslab/graph
$ cd ~/cslab/graph
$ node -v
v22.14.0

node が無ければ、Node.js を入れる手順 を先に見てください。

npm の依存関係

パッケージを1つ入れて、依存を表示させます。

bash
$ mkdir -p ~/cslab/graph/npmdemo
$ cd ~/cslab/graph/npmdemo
$ npm init -y > /dev/null
$ npm install express --no-audit --no-fund
added 68 packages in 9s

express は1つしか入れていないのに、68個入りました。 中身を見ます。

bash
$ npm ls --all | head -30
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 の数を数えてみます。

bash
$ npm ls --all | grep -c deduped
43

43箇所で「もう出てきた」と言っています。 実体は 65 パッケージなのに、木として描くと 127 行になる。その差が、木とグラフの差です。

Git のコミット履歴

次は Git です。 練習用のリポジトリを作って、枝を分けて、合流させます。

bash
$ mkdir -p ~/cslab/graph/gitdemo
$ cd ~/cslab/graph/gitdemo
$ git init -b main
$ git config user.email demo@example.com
$ git config user.name demo
$ echo 1 > a.txt && git add . && git commit -m "最初のコミット"
$ echo 2 >> a.txt && git commit -am "READMEを足す"
$ git checkout -b feature
$ echo f > f.txt && git add . && git commit -m "機能を作る"
$ git checkout main
$ echo m > m.txt && git add . && git commit -m "mainを直す"
$ git merge --no-ff feature -m "featureを取り込む"

そして履歴を図で出します。

bash
$ git log --graph --oneline --all
*   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 も同じです。 サービスが頂点、依存が有向の辺です。

bash
$ cd ~/cslab/graph
$ nano compose.yml
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.png npm 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 ]

両方書きます。

bash
$ cd ~/cslab/graph
$ nano graph.mjs
// 隣接リスト: 各頂点の「隣」を配列で持つ
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のグラフで、両方のメモリを測ります。

bash
$ nano mem.mjs
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)} %`);
bash
$ node --expose-gc mem.mjs
隣接リスト: 107.6 KB
隣接行列 : 1017.4 KB
頂点 1000 / 辺 4996
行列のマス数: 1,000,000
実際に埋まっているマス: 9,992
埋まっている割合: 1.00 %

行列は 1,000,000 マス用意して、埋まっているのは 1% です。

表し方メモリマス数使用率
隣接リスト107.6 KB—辺の分だけ
隣接行列1017.4 KB1,000,0001.00 %

約9.5倍。 そしてこれは Uint8Array(1マス1バイト)を使った場合の数字です。 普通の配列(Array に数値を入れる)にすると、1マス8バイトになってさらに8倍になります。

頂点が10倍になると、行列のメモリは100倍になる。 n² だからです。 頂点10万の SNS を行列で持つと、100億マス。現実的ではありません。

「繋がっているか」の判定を実測する

では行列は要らないのか。 そうではありません。問い合わせの速さが逆転します。

bash
$ nano hasedge.mjs
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`
  );
}
bash
$ node hasedge.mjs
辺   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)を使います。

bash
$ nano sample.mjs
// この記事で使う無向グラフ(隣接リスト)
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

③ 有向と無向 — 辿れる先が変わる

「フォロー」は有向です。 片思いがあります。 「友達」は無向です。 片方だけ友達、はありません。

同じデータから両方を作って、違いを出します。

bash
$ nano direction.mjs
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)}`);
}
bash
$ node direction.mjs
--- 有向(フォロー) ---
あきら → みなみ
みなみ → かおる
かおる → あきら
しおり → あきら
ゆう → しおり
--- 無向(友達) ---
あきら → みなみ, かおる, しおり
みなみ → あきら, かおる
かおる → みなみ, あきら
しおり → あきら, ゆう
ゆう → しおり
--- 次数 ---
あきら: 出次数 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

書きます。

bash
$ nano search.mjs
// 前の回で作ったキュー(先頭を 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) が真なら、もう見た頂点です。

走らせます。

bash
$ nano run-bfs.mjs
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(" → "));
bash
$ node run-bfs.mjs
訪問順: 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 と並べます。

bash
$ nano compare.mjs
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} 本)`);
bash
$ node compare.mjs
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。 ここが最初の分かれ道です。

深いグラフで再帰版が落ちる

一直線のグラフを作って、両方に流します。

bash
$ nano deep.mjs
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} 頂点`);
}
bash
$ node deep.mjs
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.png node compare.mjs の出力全体。 BFS と DFS の訪問順が並び、A → F が「1本」と「5本」になっているところが写るように撮ってください。


⑥ 訪問済みを忘れると止まらない

ここがこの記事の中心です。

導入で書いたとおり、私はこれで pkill node しました。同じことを、安全に再現します。

本当に無限ループさせると、ターミナルが固まって記事どころではありません。 回数の上限を付けて、超えたら例外にします。

bash
$ nano noflag.mjs
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(" → "));
bash
$ node noflag.mjs
止めました: 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色に塗り分けます。

白 = まだ行っていない
灰 = いま辿っている道の上にいる  ← ここに戻ったら輪
黒 = 辿り終わった

「灰の頂点に着いた」=「いま来た道を遡ると自分に戻れる」= 輪です。 黒はダメです。 黒は「別の道からも行ける」だけで、輪ではありません。

bash
$ nano deps.mjs
// 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;                      // 依存先が先に来る=起動してよい順
}
bash
$ nano run-deps.mjs
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);
}
bash
$ node run-deps.mjs
--- 輪があるか ---
DEPS  : 輪なし
CYCLIC: web → api → cache → web
--- 起動してよい順(トポロジカルソート) ---
db → cache → api → web → queue → worker
--- 輪があるグラフでやると ---
輪があるので順番を決められません: web → api → cache → web

web → api → cache → web と、輪の中身をそのまま出せました。

「輪がある」だけでは直せません。 どの辺を切ればいいかが分かるように、輪の頂点を並べて返すのが大事です。

3. 本物の compose.yml から検出する

手で書き写すのではなく、ファイルから読みます。

bash
$ nano read-compose.mjs
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(" → ")}` : "輪なし");
bash
$ node read-compose.mjs
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. 連結成分(島がいくつあるか)

「全員に届くか」を調べるのが連結成分です。

bash
$ nano islands.mjs
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}頂点)`));
bash
$ node islands.mjs
島の数: 3
島1: A, B, C (3頂点)
島2: D, E (2頂点)
島3: F (1頂点)

「まだ見ていない頂点があれば、そこから新しい探索を始める」だけです。

BFS でも DFS でも同じ結果になります。 順番が違うだけで、島の分け方は変わりません。

実務でどこに出るか:

場面島が2つ以上あると
ネットワークの疎通届かないセグメントがある
SNSの友達関係孤立したグループがいる
依存グラフ使われていないモジュールの塊が見つかる
クラスタのノードスプリットブレイン(両側が「自分が正しい」と思う)

使い分けの表

やりたいこと使う理由
最短経路(重みなし)BFS近い順に広げるから、初めて着いたときが最短
とにかく全部辿るどちらでも訪問順が違うだけ
循環の検出DFS「いま辿っている道」が分かるのは DFS だけ
トポロジカルソートDFS帰りがけに積むだけで順序になる
連結成分どちらでも未訪問から始め直すだけ
深さが読めないデータBFS かループ版 DFS再帰版はスタックが溢れる
メモリが厳しいDFSBFS は「その距離の頂点全部」をキューに載せる

最後の行は見落としやすい点です。 BFS は横に広いグラフで、キューが一気に膨らみます。 SNS のように「1人が1万人フォロー」だと、距離1の時点で1万件です。

スクリーンショットを撮ってください: 03_cycle_topo.png node run-deps.mjs と node read-compose.mjs の出力。 web → api → cache → web の輪と、db → cache → api → web の起動順が両方見えるように撮ってください。


⑧ 全域木 — 探索した跡が、そのまま木になる

全域木とは、「すべての頂点を、輪を作らずに繋ぐ辺の集まり」です。

そして、これは新しく作るものではありません。 BFS や DFS を1回回せば、勝手にできています。 prev(どこから来たか)がそれです。

bash
$ nano spanning.mjs
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} 本`);
bash
$ node spanning.mjs
元のグラフ: 頂点 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 も入っているので、まとめて消えます。

bash
$ cd ~
$ rm -rf ~/cslab/graph
$ ls ~/cslab

graph が消えていれば完了です。

gitdemo の中で git を試した人は、リポジトリごと消えています。 消したくないものを ~/cslab/graph の中に置いていないか、消す前に確認してください。

bash
$ du -sh ~/cslab 2>/dev/null || echo "cslab はもうありません"

まとめ — 理解できたこと

  • グラフは「点と、それを繋ぐ線」だけ。 数式は要らない
  • 木はグラフの一種にすぎない。 「輪にならない」という条件が付いただけ
  • 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 本

参考リンク


次に読む

この記事は 【深掘り】コンピュータ科学 の 13 / 25 本目です。

記事
← 前の記事線形探索と二分探索 — 1回引くだけなら並べると損
→ 次の記事最短経路アルゴリズム — ダイクストラは負の重みで壊れる

上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。

全体の順路は はじめに にあります。

roadmap.sh のどこをやっているか

›CS — Graphs
  • 隣接リストと隣接行列を実測で選ぶ
  • 訪問済みを忘れると止まらない

この記事は、上の項目を実際に手を動かして確かめる回です。

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

目次