TypeScriptでトポロジカルソートを実装する：Kahnのアルゴリズムを不変条件とテストで確かめる

ライブコーディング支援という利用文脈の出典: AIコーディング面接アシスタント。本稿はそこから独立して書き直した、トポロジカルソートの実装解説です。

依存関係を順序に直すとき、DFS より説明しやすく、循環も同時に検出できるのが Kahn のアルゴリズムです。本稿では TypeScript で実装し、次の三点をテストします。

• 依存先より必ず後に出力される
• 孤立した頂点や「出辺だけに現れる頂点」も落とさない
• 循環があれば、部分的な順序を返さず失敗させる

計算量は頂点数を (V)、辺数を (E) として (O(V + E)) です。ビルド順、ジョブの実行順、科目の履修順のように「先に終えるもの」がある場面で使えます。

Kahn のアルゴリズムの不変条件

有向辺 A -> B を「A が終わるまで B は開始できない」と読みます。このとき B の 入次数（in-degree） は、まだ処理されていない前提条件の数です。

アルゴリズムは次を繰り返します。

1. 入次数が 0 の頂点をキューに入れる
2. 1 つ取り出して結果へ追加する
3. その頂点から出る辺を削除したものとして、行き先の入次数を 1 減らす
4. 入次数が 0 になった頂点をキューに追加する

重要な不変条件は「キューにある頂点は、未処理の前提条件を持たない」です。この条件が保たれるため、出力順は常に正しいトポロジカル順序になります。

逆に、キューが空なのに未処理の頂点が残るなら、それらは互いに依存しているため循環があります。

実装

入力は node -> その node の後に実行できる node 群 という隣接リストです。キューを辞書順に保つのは、アルゴリズムに必須ではありません。同率の候補があるときに出力を再現可能にし、テストやログの差分を安定させるためです。

export class CycleError extends Error {
  constructor(public readonly nodes: readonly string[]) {
    super(`cycle detected: ${nodes.join(", ")}`);
    this.name = "CycleError";
  }
}

function enqueueSorted(queue: string[], node: string) {
  const index = queue.findIndex((item) => item > node);

  if (index === -1) {
    queue.push(node);
  } else {
    queue.splice(index, 0, node);
  }
}

export function topologicalSort(
  graph: ReadonlyMap<string, readonly string[]>,
): string[] {
  const inDegree = new Map<string, number>();

  for (const [node, nextNodes] of graph) {
    inDegree.set(node, inDegree.get(node) ?? 0);

    for (const next of nextNodes) {
      inDegree.set(next, (inDegree.get(next) ?? 0) + 1);
    }
  }

  const queue = [...inDegree]
    .filter(([, degree]) => degree === 0)
    .map(([node]) => node)
    .sort();
  const result: string[] = [];

  while (queue.length > 0) {
    const node = queue.shift();

    if (node === undefined) {
      break;
    }

    result.push(node);

    for (const next of graph.get(node) ?? []) {
      const degree = (inDegree.get(next) ?? 0) - 1;
      inDegree.set(next, degree);

      if (degree === 0) {
        enqueueSorted(queue, next);
      }
    }
  }

  if (result.length !== inDegree.size) {
    const nodes = [...inDegree]
      .filter(([, degree]) => degree > 0)
      .map(([node]) => node)
      .sort();

    throw new CycleError(nodes);
  }

  return result;
}

ここで inDegree.set(node, inDegree.get(node) ?? 0) を先に置いています。これにより、キーとして現れるだけの頂点も保持できます。また、辺の終点だけに現れる頂点も、内側のループで必ず登録されます。

Bun で確かめる

順序そのものだけでなく、「各辺の始点が終点より前にある」という性質を検査します。これなら、同率候補の順番を変えても本質的な正しさを確認できます。

import { expect, test } from "bun:test";
import { CycleError, topologicalSort } from "./topological-sort";

test("依存関係を満たす順序を返す", () => {
  const graph = new Map<string, string[]>([
    ["build", ["test", "package"]],
    ["lint", ["test"]],
    ["test", ["deploy"]],
    ["package", ["deploy"]],
  ]);

  const order = topologicalSort(graph);
  const position = new Map(order.map((node, index) => [node, index]));

  for (const [from, nextNodes] of graph) {
    for (const to of nextNodes) {
      expect(position.get(from)).toBeLessThan(position.get(to));
    }
  }

  expect(order).toEqual(["build", "lint", "package", "test", "deploy"]);
});

test("出辺だけに現れる頂点も含める", () => {
  const order = topologicalSort(new Map([["compile", ["bundle"]]]));

  expect(order).toEqual(["compile", "bundle"]);
});

test("循環は部分結果ではなく例外にする", () => {
  const graph = new Map([
    ["A", ["B"]],
    ["B", ["C"]],
    ["C", ["A"]],
  ]);

  expect(() => topologicalSort(graph)).toThrow(CycleError);
});

bun test

DFS 実装との使い分け

DFS の後順で作る実装も (O(V + E)) ですが、実行順を説明する場面では Kahn のほうが状態を追いやすいことがあります。

観点	Kahn	DFS
次に実行可能な頂点	入次数 0 のキューとして見える	再帰の戻り時まで見えにくい
循環の検出	処理数が頂点数に届かない	visiting 状態の管理が必要
並列実行の設計	キュー内の複数頂点を候補にできる	別途スケジューリングが必要

ただし、実運用でキュー内の頂点を並列に実行するなら、トポロジカルソートは「候補を出す」だけです。実行数の上限、失敗時の再試行、同じジョブの重複実行防止は別に設計します。

面接で説明するなら

短く説明するなら、次の順で十分です。

1. 各頂点の未解決の前提条件数を入次数として数える
2. 入次数 0 の頂点だけを処理可能なキューに置く
3. 取り出すたびに隣接頂点の入次数を減らす
4. 最後に処理数が頂点数に届かなければ循環と判断する

「なぜ正しいか」と聞かれたら、キューに入る時点で全ての前提条件が結果へ追加済み、という不変条件を答えると実装の説明が締まります。

まとめ

Kahn のアルゴリズムは、入次数 0 の頂点を前から確定させることで、依存関係を安全な順序へ変換します。実装では、終点だけに現れる頂点を忘れないこと、循環時に部分結果を成功として返さないこと、同率候補の順序を必要に応じて固定することが実務上の要点です。