グラフ理論：強連結成分（SCC）

目次

インタラクティブ

Tarjan は相互到達可能な頂点を SCC にまとめる

次の SCC自動リセット

有向グラフ

「次の SCC」を押して最初の成分を表示します。

SCC を縮約すると有向非巡回グラフ (DAG) になる

タージャン法で求める強連結成分

有向グラフで、二つの頂点が互いに到達可能なら強連結であるといいます。**強連結成分（SCC）**は、この相互到達性を満たす頂点の極大集合です。各 SCC を一つの頂点にまとめると有向非巡回グラフになり、依存関係や到達性の解析に役立ちます。

タージャン法の一回の探索

タージャン法は深さ優先探索（DFS）一回で、すべての SCC を O(V + E) 時間で求めます。頂点 v の index[v] は発見順を表す番号です。lowLink[v] は DFS 木の辺をたどり、最後にまだ有効スタックにある頂点への辺を最大一度たどって到達できる、最小の発見番号です。

DFS 木の子の探索が終わると、親は子の lowLink を反映します。まだスタックに残る頂点への辺では、その頂点の index を使います。すでにスタックから取り除かれた頂点への辺は無視します。有効スタックは再帰呼び出しのスタックとは別物で、SCC が確定していない頂点を保持します。

lowLink[v] === index[v] なら、v の DFS 部分木から到達できる頂点は、より前の有効頂点へ戻れません。したがって v は SCC の根です。有効スタックから v まで取り出した頂点が、その SCC を構成します。外側のループは未訪問の各頂点からも探索を始めるため、互いにつながっていない部分も漏れなく処理します。

JavaScript 実装

関数は隣接リスト graph を受け取ります。graph[u] には、u から出る辺の行き先を0始まりの頂点番号で並べます。すべての行き先が有効な番号であることを前提とします。戻り値は0始まりの頂点番号の配列からなるリストで、成分や成分内の順番は一定ではありません。

function stronglyConnectedComponents(graph) {
  const n = graph.length;
  const index = Array(n).fill(-1);
  const lowLink = Array(n).fill(0);
  const onStack = Array(n).fill(false);
  const stack = [];
  const components = [];
  let nextIndex = 0;

  function visit(v) {
    index[v] = nextIndex;
    lowLink[v] = nextIndex;
    nextIndex += 1;
    stack.push(v);
    onStack[v] = true;

    for (const w of graph[v]) {
      if (index[w] === -1) {
        visit(w);
        lowLink[v] = Math.min(lowLink[v], lowLink[w]);
      } else if (onStack[w]) {
        lowLink[v] = Math.min(lowLink[v], index[w]);
      }
    }

    if (lowLink[v] === index[v]) {
      const component = [];
      let w;
      do {
        w = stack.pop();
        onStack[w] = false;
        component.push(w);
      } while (w !== v);
      components.push(component);
    }
  }

  for (let v = 0; v < n; v += 1) {
    if (index[v] === -1) visit(v);
  }

  return components;
}

辺が 0→1、1→2、2→0、2→3、3→4、4→3、4→5 のグラフでは、結果は {0,1,2}、{3,4}、{5} です（順番は問いません）。最初の三頂点は一つの閉路を作り、3と4も互いに行き来できます。5から到達でき、さらに5へ戻れる頂点はありません。

時間計算量は O(V + E)、補助空間計算量は O(V) です。この実装は再帰を使うため、呼び出しの深さは O(V) になり得ます。非常に深いグラフでは JavaScript 実行環境のコールスタック上限を超える可能性があるため、その場合は反復型 DFS を検討してください。

要点： 発見番号は探索順を、low-link は到達可能な最も早い有効頂点を表します。low-link が根の発見番号と一致すると、その SCC を取り出します。