TypeScriptでTarjanの強連結成分分解を実装する：lowlinkの不変条件をテストで確かめる

背景となる面接文脈は、ライブコーディング面接で問われる説明の違いにあります。本稿はそこから独立して書き下ろした、強連結成分の技術解説です。

有向グラフに循環依存があるとき、「どの頂点が同じ循環の中にいるか」を一度の探索で取り出すのが Tarjan の強連結成分（SCC）分解です。

この記事では、TypeScript で実行可能な実装を書き、次の三つを説明します。

• lowlink が何を表すか
• なぜ lowlink[v] === index[v] で一つの成分を取り出せるか
• 実装の壊れやすい境界をどうテストするか

先に結論

• 強連結成分は「互いに行き来できる頂点の最大集合」です。
• Tarjan 法は DFS を一度だけ行い、時間計算量 O(V + E)、追加領域 O(V) で SCC を求めます。
• 探索中のスタックに残る頂点だけを lowlink の候補にすることが重要です。すでに取り出した成分へ向かう辺を混ぜると、別の成分を誤って一つにしてしまいます。

例えば図では A, B, C が一つの SCC、D, E がもう一つの SCC、F は単独の SCC です。C -> D はあっても D 側から A 側へ戻れないため、二つの成分は結合しません。

どんな場面で使うか

SCC は、技術面接では「依存グラフの循環をどう扱うか」という質問で自然に登場します。

• モジュール依存を縮約し、循環している単位を一つの塊として扱う
• ジョブ間の依存関係で、実行不能な循環を特定する
• 状態遷移グラフで、相互に到達可能な状態をまとめる
• 通信経路で双方向に到達できるサービス群を調べる

Kahn 法のトポロジカルソートは「グラフ全体が DAG か」を判定するには便利です。しかし循環が見つかった後に、どの頂点が同じ循環の原因かまで分けて欲しいなら SCC が必要になります。

3つの状態と不変条件

実装に入る前に、各頂点について保持する値を固定します。

値	意味
index[v]	v を最初に訪れた順番。未訪問なら値を持たない
lowlink[v]	DFS 部分木から、探索スタック上にある頂点へ戻れる最小の index
onStack(v)	v がまだ SCC として確定していないこと

ここでの不変条件は次の通りです。

1. スタック上の頂点は、現在の DFS から到達したものだけです。
2. 子 to を探索し終えたら、lowlink[from] は lowlink[to] まで下がり得ます。
3. 既訪問の to がまだスタック上なら、from は index[to] まで戻れます。
4. lowlink[v] === index[v] なら、v は現在の SCC の根です。スタックの先頭から v までを取り出せます。

3 番目の「まだスタック上」が抜けやすい点です。すでに出力済みの SCC は DFS の現在経路には属しません。その頂点への辺を back edge のように扱うと、成分の境界を壊します。

実装

以下は文字列の頂点を扱う最小実装です。グラフ構築時に addEdge が両端を登録するため、出辺がない頂点も失われません。

class TarjanScc {
  #edges = new Map<string, string[]>();

  addVertex(vertex: string): this {
    if (!this.#edges.has(vertex)) this.#edges.set(vertex, []);
    return this;
  }

  addEdge(from: string, to: string): this {
    this.addVertex(from);
    this.addVertex(to);
    this.#edges.get(from)!.push(to);
    return this;
  }

  components(): string[][] {
    let nextIndex = 0;
    const index = new Map<string, number>();
    const lowlink = new Map<string, number>();
    const stack: string[] = [];
    const onStack = new Set<string>();
    const result: string[][] = [];

    const visit = (vertex: string): void => {
      index.set(vertex, nextIndex);
      lowlink.set(vertex, nextIndex);
      nextIndex++;
      stack.push(vertex);
      onStack.add(vertex);

      for (const next of this.#edges.get(vertex)!) {
        if (!index.has(next)) {
          visit(next);
          lowlink.set(
            vertex,
            Math.min(lowlink.get(vertex)!, lowlink.get(next)!),
          );
        } else if (onStack.has(next)) {
          lowlink.set(
            vertex,
            Math.min(lowlink.get(vertex)!, index.get(next)!),
          );
        }
      }

      if (lowlink.get(vertex) !== index.get(vertex)) return;

      const component: string[] = [];
      while (true) {
        const member = stack.pop()!;
        onStack.delete(member);
        component.push(member);
        if (member === vertex) break;
      }
      result.push(component);
    };

    for (const vertex of this.#edges.keys()) {
      if (!index.has(vertex)) visit(vertex);
    }
    return result;
  }
}

なぜ二種類の min があるのか

未訪問の子を再帰で処理した後は、その子の部分木が持つ戻り道を引き継ぐため lowlink[next] を使います。

一方で、すでに訪問済みかつスタック上の頂点への辺は、現在の探索経路に直接戻る辺です。この場合に使うのは lowlink[next] ではなく、発見順そのものの index[next] です。

if (!index.has(next)) {
  visit(next);
  // 子の部分木が持つ戻り道を反映する
  lowlink.set(vertex, Math.min(lowlink.get(vertex)!, lowlink.get(next)!));
} else if (onStack.has(next)) {
  // 現在の DFS 経路への辺なので、到着先の発見順を見る
  lowlink.set(vertex, Math.min(lowlink.get(vertex)!, index.get(next)!));
}

この分岐を「既訪問なら常に lowlink[next]」と書くと、別の DFS 枝から得た情報まで混ざります。Tarjan 法では、スタックが「まだ確定していない候補だけ」を表すこと自体が正しさの一部です。

動作を確認するテスト

成分内の頂点順は DFS の順番で変わり得ます。テストでは比較の前だけ整列し、アルゴリズム本体の計算量を余計なソートで変えないようにします。

import { strict as assert } from "node:assert";

const normalized = (components: string[][]) =>
  components
    .map((component) => component.toSorted())
    .toSorted((a, b) => a.join(",").localeCompare(b.join(",")));

const graph = new TarjanScc()
  .addEdge("A", "B")
  .addEdge("B", "C")
  .addEdge("C", "A")
  .addEdge("C", "D")
  .addEdge("D", "E")
  .addEdge("E", "D")
  .addVertex("F");

assert.deepEqual(
  normalized(graph.components()),
  [["A", "B", "C"], ["D", "E"], ["F"]],
);

// 自己ループは 1 頂点の SCC
assert.deepEqual(
  normalized(new TarjanScc().addEdge("X", "X").components()),
  [["X"]],
);

// 一方向の辺だけでは同じ SCC にならない
assert.deepEqual(
  normalized(new TarjanScc().addEdge("P", "Q").components()),
  [["P"], ["Q"]],
);

// 空グラフ
assert.deepEqual(normalized(new TarjanScc().components()), []);

Bun でこのファイルを実行し、4 ケースすべてが通ることを確認しました。

Tarjan SCC: 4 test cases passed

面接で説明する順番

ホワイトボードや口頭で説明するなら、コードから始めるより次の順番が伝わりやすいです。

1. 「相互に到達できる頂点の塊」を求めたい、と SCC を定義します。
2. DFS の訪問順を index、未確定頂点を stack で保持すると述べます。
3. lowlink を「現在の候補成分から戻れる最も古い訪問順」と説明します。
4. lowlink === index の頂点でスタックを切れば、そこが一つの最大成分になると示します。
5. 全頂点と全辺を一度ずつ見るため O(V + E) と締めます。

実装を暗記するより、onStack が成分の境界を守る理由まで説明できると、循環依存やジョブ実行順の設計問題にも応用しやすくなります。

まとめ

Tarjan 法の本質は、DFS の途中にある頂点だけをスタックに残し、lowlink で「どこまで戻れるか」を追跡することです。

• lowlink の更新は、未訪問の子とスタック上の既訪問頂点で分けます。
• 根を見つけたら、スタックからまとめて取り出します。
• 一方向の辺、自己ループ、孤立頂点をテストすると、境界の誤りを早めに見つけられます。

依存グラフの循環を「ある / ない」だけで終わらせず、構成要素ごとに切り分けたい場面で使える実装です。