グラフと探索 — つながりをたどる

マイクロサービスの起動順を決めたい。権限がどこまで継承されているか調べたい。循環インポートがどこで閉じているか知りたい。

これらは見た目の違う問題ですが、「点と、点をつなぐ線」に置き換えると同じ 1 つの問題になります。グラフはその置き換えのための言葉です。

この章で学ぶこと

グラフの語彙と、隣接リスト・隣接行列の使い分け
幅優先探索が重みなしの最短経路になる理由
深さ優先探索と、訪問済み集合が無いと止まらないこと
トポロジカルソートで依存関係を並べ、循環を検出する
「状態」を頂点と見なして探索に持ち込む発想

前提知識

頂点と辺

グラフは 頂点 (ノード) と、頂点をつなぐ 辺 (エッジ) でできています。区別が要るのは 2 点だけです。

区別	意味	例
有向 / 無向	辺に向きがあるか	「A は B をインポートする」は有向。「A と B は友達」は無向
重みあり / なし	辺にコストが付くか	「乗り換え回数」は重みなし。「所要時間」は重みあり

木はグラフの特殊な形です。データ構造の章で扱った木は、「閉路がなく、すべての頂点がつながっている」グラフのことです。だから木をたどるコードは、そのままグラフには使えません。グラフには閉路がありうるぶんの手当てが要ります。

2 つの表し方

// 隣接リスト: 頂点ごとに「つながっている先」を持つ
type Graph = Map<string, string[]>;

const graph: Graph = new Map([
  ["A", ["B", "C"]],
  ["B", ["A", "D"]],
  ["C", ["A", "D"]],
  ["D", ["B", "C", "E"]],
  ["E", ["D"]],
]);

もう 1 つは 隣接行列 で、行 × 列 の表に辺の有無を入れます。

	隣接リスト	隣接行列
記憶域	`O(V + E)`	`O(V²)`
「A と B は隣接か」	`O(A の次数)`	`O(1)`
「A の隣を全部」	`O(A の次数)`	`O(V)`

V は頂点数、E は辺の数です。実務で出てくるグラフはたいてい疎 — 頂点数のわりに辺が少ない — なので、隣接リストが既定です。隣接行列が有利なのは、頂点数が小さく辺が密なときと、「この 2 点は隣接か」を大量に問い合わせるときです。

幅優先探索 — 近いところから広げる

キューを使って、出発点から近い順に層をなして広げます。

function bfsDistances(g: Graph, start: string): Map<string, number> {
  const dist = new Map<string, number>([[start, 0]]);
  const queue: string[] = [start];
  for (let head = 0; head < queue.length; head++) {
    const v = queue[head];
    for (const next of g.get(v) ?? []) {
      if (dist.has(next)) continue; // 既に距離が確定している = 訪問済み
      dist.set(next, (dist.get(v) as number) + 1);
      queue.push(next);
    }
  }
  return dist;
}

const d = bfsDistances(graph, "A");
console.log([...d].map(([v, n]) => `${v}=${n}`).join(" "));
// A=0 B=1 C=1 D=2 E=3

A から D へは A→B→D と A→C→D の 2 通りありますが、どちらも 2 手なので D=2 です。

この距離が最短だと言えるのは、層を飛び越さないからです。キューは先に入れたものから出るので、距離 1 の頂点をすべて処理してから距離 2 に進みます。ある頂点に最初に到達したときの距離が最短で、あとから別の経路で来ても更新は要りません。上のコードで dist.has(next) を見て continue しているのがその判断です。

深さ優先探索 — 行けるところまで行く

進めるだけ先に進み、行き止まりで 1 つ戻ります。再帰で書くのが素直です。

function dfsOrder(g: Graph, start: string): string[] {
  const seen = new Set<string>();
  const order: string[] = [];
  function visit(v: string): void {
    if (seen.has(v)) return; // これが無いと閉路で止まらない
    seen.add(v);
    order.push(v);
    for (const next of g.get(v) ?? []) visit(next);
  }
  visit(start);
  return order;
}

console.log(dfsOrder(graph, "A").join(" -> "));
// A -> B -> D -> C -> E

A の隣は B と C ですが、B に入ったあとは戻らずに D まで進み、D から C へ回っています。訪問の順序が BFS とまったく違う点に注意してください。

再帰で書けば呼び出しスタックが「戻る場所」を覚えてくれます。明示的なスタックに置き換えることもでき、そのときは再帰と分割統治の章で見たスタックの深さの問題を自分で管理することになります。

訪問済みを持たないと止まらない

上の 2 つのコードは、どちらも訪問済みの記録を持っています。これは省略できません。

グラフには閉路があります。A → B → D → C → A のような環を、訪問済みを持たずにたどると同じ頂点を回り続けます。木をたどるコードをそのままグラフに流用すると、この形で無限ループか RangeError になります。

**訪問済みは「入れる場所」も重要です。**キューに入れる時点で記録しないと、同じ頂点が複数回キューに積まれます。上の BFS は dist に入れた時点で訪問済み扱いにしているので、二重に積まれません。

計算量

どちらも O(V + E) です。各頂点を 1 回ずつ訪問し、各辺を 1 回ずつ (無向なら両端から 1 回ずつ) 見るからです。

**O(V × E) ではありません。**辺をたどる回数の合計が辺の数に比例して収まる、というのが要点です。無向グラフでは頂点ごとの次数を足し合わせると辺の数の 2 倍になり、各辺を両端から 1 回ずつ見ることに対応します。

重みが違うと BFS では最短にならない

BFS が最短経路を出すのは、すべての辺の重みが等しいときだけです。

乗り換え回数を最小にしたいなら BFS で正しい。しかし所要時間を最小にしたい場合、「1 本の長い辺」より「2 本の短い辺」のほうが速いことがあります。BFS は手数だけを見るので、この逆転を扱えません。

重みが違う場合はダイクストラ法を使います。「次に確定させるのは、まだ確定していない中で最も距離が小さい頂点」という規則で、キューを優先度付きキューに置き換えた形です。負の重みがある場合はさらに別の方法が要ります。

**この章では実装まで踏み込みません。**押さえるべきは境界です — 辺の重みが等しいなら BFS、違うならダイクストラ。

状態を頂点と見なす

グラフは「もともと点と線で表されているもの」だけの道具ではありません。取りうる状態を頂点、状態の遷移を辺と見なすと、探索の問題に置き換わります。

問題	頂点	辺
パズルの最短手数	盤面	1 手動かすこと
単語を 1 文字ずつ変えて別の単語にする	単語	1 文字の書き換え
権限がどこまで継承されるか	ロール	「継承する」関係

「最短の手数」を問われたら BFS、というのがこの置き換えの実益です。状態の数が有限で、1 手のコストが等しいからです。

注意すべきは状態の数です。盤面の組合せは指数で増えるので、そのまま全部を頂点にすると探索が終わりません。実務で使うときは、状態を正規化して同じものをまとめるか、探索する範囲を絞ります。

依存関係の順序と、循環の検出

有向グラフで「先に終わらせるもの」から順に並べるのがトポロジカルソートです。ビルドの順序、マイグレーションの適用順、初期化の順序がこれに当たります。

// 「A の前に B を終わらせる」= A から B への辺
const deps: Graph = new Map([
  ["config", []],
  ["db", ["config"]],
  ["api", ["db", "config"]],
  ["web", ["api"]],
]);

function topoSort(g: Graph): string[] | null {
  const state = new Map<string, 0 | 1 | 2>(); // 0 未訪問 / 1 訪問中 / 2 完了
  const order: string[] = [];
  let cyclic = false;

  function visit(v: string): void {
    const s = state.get(v) ?? 0;
    if (s === 2) return;
    if (s === 1) { cyclic = true; return; } // 訪問中の頂点へ戻った = 閉路
    state.set(v, 1);
    for (const next of g.get(v) ?? []) visit(next);
    state.set(v, 2);
    order.push(v); // すべての依存を終えてから自分を積む
  }

  for (const v of g.keys()) visit(v);
  return cyclic ? null : order;
}

console.log(topoSort(deps)?.join(" -> "));
// config -> db -> api -> web

const cyclicGraph: Graph = new Map([["a", ["b"]], ["b", ["c"]], ["c", ["a"]]]);
console.log(topoSort(cyclicGraph) === null ? "閉路あり" : "閉路なし");
// 閉路あり

訪問済みを 2 値でなく 3 値で持つのがこの実装の要点です。「完了」に戻ったのは単に別の経路から再訪しただけで問題ありません。「訪問中」に戻ったときだけが閉路です。2 値のフラグでは、この 2 つを区別できません。

たとえば a→b、a→c、b→d、c→d という閉路の無いグラフでは、d に 2 通りの経路で到達します。2 値で「再訪はすべて閉路」と判定すると、このグラフを閉路ありと誤判定します。

書き方はこれだけではありません。「入ってくる辺が 0 本の頂点」から順に剥がしていく方法もあります。剥がすたびに行き先の入次数を 1 減らし、0 になったものをキューに入れる — この章の前半で見た幅優先探索と同じ形です。出力できた頂点数が全体より少なければ閉路があると分かるので、3 値の状態は要りません。深い再帰を避けたいときはこちらを選びます。

循環依存の検出は実務でそのまま使えます。たとえばタスクの依存関係をユーザーが自由に登録できるとき、データベース設計ガイドの実践編が扱っているとおり、データベースの制約で循環を防ぐのは複雑なので、アプリケーション側で登録前に検出することになります。

判断の手順

問い	選ぶもの
最短の手数・最少の乗り換えは	BFS
到達できるか、全経路を列挙したいか	DFS (メモリが少なく済む)
依存関係の実行順が欲しい	トポロジカルソート
循環しているか知りたい	DFS なら 3 値の状態を持つ (入次数を剥がす書き方なら不要)
辺ごとにコストが違う最短経路	ダイクストラ (BFS では出ない)

探索の前に必ず決めることが 2 つあります。

何を頂点にするか — もとのデータのままか、状態に置き換えるか
訪問済みをどこで記録するか — キューに入れる時点か、取り出す時点か

よくある誤解

「DFS でも最短経路が出る」 — 出ません。DFS が最初に見つけた経路は「たまたま先に行き止まらなかった経路」で、長さの保証がありません。最短が要るなら BFS です。

「訪問済みは高速化のため」 — **正しさのためです。**無向グラフや閉路のあるグラフでは、無いと終わりません。

「グラフは特殊なデータ構造」 — 隣接リストは Map<頂点, 頂点[]> にすぎません。専用のライブラリを入れる前に、手元のデータがすでにグラフの形をしていないか見てください。外部キーでつながったテーブル、インポート文、ロールの継承はすべてグラフです。

「木のコードをグラフに流用できる」 — 木は閉路のないグラフなので、木のコードには訪問済みの管理がありません。そのままグラフに当てると止まらなくなります。

確認問題

問 1. 権限のロールが「一般 → 編集者 → 管理者」と継承される設計で、あるユーザーが特定の操作を行えるか判定したい。BFS と DFS のどちらで書きますか。

答え: どちらでもかまいません。到達できるかどうかだけを見るからです。

「行えるか」は到達可能性の問いで、経路の長さを問いません。最短が要らないので BFS の利点が効かず、どちらでも同じ答えが出ます。

選ぶ基準は別のところにあります。

DFS (再帰) — コードが短い。継承の階層が浅いなら素直
BFS — 階層が深くなりうるなら、スタックを気にせず済む

**むしろ重要なのは訪問済みの管理です。**ロールの継承は設定ミスで循環しえます (「A は B を継承、B は A を継承」)。訪問済みを持たなければ、その設定が入った瞬間に判定処理が止まります。

判定を高速にしたいなら、探索そのものを毎回走らせず、ロールごとに「到達できる権限の集合」を事前に展開して持つ方法もあります。ただし継承を変更したときに再計算が要るので、変更の頻度と判定の頻度で選びます。

問 2. ある頂点から別の頂点への「最少の乗り換え回数」を BFS で求めました。同じコードで「最短の所要時間」も出せますか。

答え: 出せません。辺の重みが等しくないからです。

BFS が最短を保証する根拠は、層を飛び越さないことにあります。距離 1 をすべて処理してから距離 2 に進むので、最初に到達した時点が最短になります。

所要時間では辺ごとにコストが違うので、この前提が崩れます。「1 本で 60 分」より「2 本で合計 20 分」のほうが速い、という逆転が起きます。BFS は本数しか数えないのでこれを見つけられません。

必要なのはダイクストラ法です。キューを優先度付きキューに変え、まだ確定していない中で最も距離が小さい頂点から確定させる規則にします。BFS はこの規則の「すべての重みが 1 の場合」に当たります。

**逆に言えば、重みがすべて等しいなら BFS で十分です。**優先度付きキューの分だけ BFS のほうが軽いので、乗り換え回数を数えるだけなら BFS を選びます。

問 3. マイグレーションの適用順をトポロジカルソートで決めています。ある日「順序が決まりません」というエラーが出ました。何が起きていて、どう調べますか。

答え: 依存関係に閉路ができています。「訪問中」の状態にある頂点へ戻った経路を出力させて特定します。

トポロジカルソートが順序を出せるのは、有向グラフに閉路がないときだけです。「A の前に B、B の前に C、C の前に A」が同時に成り立つ順序は存在しません。

調べ方は、閉路の検出そのものを利用します。3 値の状態 (未訪問 / 訪問中 / 完了) を持つ DFS で、「訪問中」の頂点に戻った瞬間の呼び出し経路が閉路です。エラーを投げるだけでなく、そのときのスタックを一緒に出力すれば、どのファイル同士が環を作っているかがそのまま分かります。

実務で起きやすいのは、依存の書き方が 2 系統あるときです。「このマイグレーションは X の後」と「X はこのマイグレーションの前」を両方書ける仕組みだと、片方だけ直したときに向きが食い違って環になります。検出したあとは、宣言の方向を 1 つに寄せるのが再発防止になります。

まとめ

グラフは頂点と辺。区別が要るのは有向 / 無向と重みあり / なしの 2 点
**木は閉路のないグラフ。**木のコードをグラフに流用すると止まらない
表し方は隣接リストが既定。隣接行列が有利なのは頂点が少なく辺が密なとき
BFS はキューで層ごとに広げるので、重みが等しいときの最短経路になる
**DFS はスタックか再帰。**最短は保証しない
**訪問済みは正しさのために要る。**高速化のためではない
どちらも O(V + E)
**辺ごとにコストが違うならダイクストラ。**BFS では出ない
状態を頂点と見なすと、パズルや文字列の問題が探索に化ける。状態数の爆発に注意
トポロジカルソートを DFS で書くなら 3 値の状態が要る。「訪問中」への再訪だけが閉路。入次数を数えて 0 のものから剥がす書き方なら 3 値は要らない

次に読む

動的計画法 — 探索の途中で同じ状態を何度も計算しているとき、何をすればよいか
データ構造の選び方 — スタックとキューの違いが、そのまま DFS と BFS の違いになる

この章で学ぶこと​

頂点と辺​

2 つの表し方​

幅優先探索 — 近いところから広げる​

深さ優先探索 — 行けるところまで行く​

訪問済みを持たないと止まらない​

計算量​

重みが違うと BFS では最短にならない​

状態を頂点と見なす​

依存関係の順序と、循環の検出​

判断の手順​

よくある誤解​

確認問題​

まとめ​

次に読む​