グラフ DFS で連結成分の数を数える｜コードで実践

グラフ DFS で連結成分の数を数える

このレッスンで分かること

DFS と BFS の差は データ構造がスタックかキューか だけ

ノード数 n、エッジ数 m に対して O(n + m)

DFS (深さ優先探索) は BFS と並ぶグラフ走査の代表アルゴリズムです

グラフ DFS で連結成分の数を数えるとは

深さ優先探索 (DFS) を使って、グラフに含まれる連結成分の個数を求める関数を実装する。本レッスンでは、グラフ DFS で連結成分の数を数えるの基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

DFS (深さ優先探索) は BFS と並ぶグラフ走査の代表アルゴリズムです。BFS が「近いノードから順に」訪問するのに対し、DFS は「行けるところまで深く進んでから戻る」というスタイルで探索します。再帰で書けば自然に表現できますし、スタックを使えば反復でも書けます。

本レッスンでは DFS を使って、グラフに 連結成分が何個あるか を数える関数 countComponents(n, edges) を作ります。連結成分とは「お互いに辺で繋がっているノードの最大の塊」のことです。SNS で言えば「友達の友達まで辿って到達可能なグループ」、地図で言えば「島」のような単位です。

連結成分の個数を数えるアルゴリズムは Union-Find でも書けるが、DFS で書くと教科書通りで読みやすい。本問題では DFS で行く。

アルゴリズムの骨格

基本アイデアはとてもシンプルです。

visited を全ノードぶん用意して初期化
ノード i を順に見て、まだ visited でなければカウンタ count を 1 増やし、そこから DFS で同成分すべてに visited を立てる
全ノードを見終わったら count が成分数

diagram (will load when visible)

図のポイント (テキスト併記)

上の例は count = 3 です

上の例は count = 3 です。0-1-2 の塊、3-4 の塊、孤立ノード 5 の合計 3 つ。

再帰 DFS の実装 (Python)

Python

import sys
sys.setrecursionlimit(100000)

def countComponents(n, edges):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    visited = [False] * n
    def dfs(u):
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                dfs(v)
    count = 0
    for i in range(n):
        if not visited[i]:
            count += 1
            dfs(i)
    return count

dfs(i) を呼ぶ回数がそのまま連結成分の個数になります。dfs の中で再帰的に隣接ノードへ降りていき、たどり着けるノード全部に visited = True を立てるので、外側のループでは「未訪問の起点」を見つけたときだけ count が増えます。

スタック版 DFS (JavaScript)

再帰の代わりにスタックで書くと、再帰の深さ制限を気にせず動かせます。実装上もそれほど難しくありません。

JavaScript

function countComponents(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }
  const visited = new Array(n).fill(false);
  let count = 0;
  for (let i = 0; i < n; i++) {
    if (visited[i]) continue;
    count++;
    const stack = [i];
    visited[i] = true;
    while (stack.length) {
      const u = stack.pop();
      for (const v of adj[u]) {
        if (!visited[v]) {
          visited[v] = true;
          stack.push(v);
        }
      }
    }
  }
  return count;
}

スタック (stack.pop()) は LIFO なので、後から入れた v が先に処理されます。BFS のキュー (FIFO) との違いは、この 取り出す順番 だけです。

計算量

ノード数 n、エッジ数 m に対して O(n + m)。BFS と同じです。visited の判定が O(1) で済むのでこの線形時間が実現できます。

DFS と BFS の差は データ構造がスタックかキューか だけ。本質は「visited を立てつつ展開していく」点で共通。

よくある間違い

1 つ目は 再帰深さ超過 です。グラフが鎖状に長いと n=10000 でも再帰で stack overflow になります。Python なら sys.setrecursionlimit を上げるか、反復版を使う。2 つ目は count += 1 を DFS の中で実行してしまうケース。本来「未訪問の起点を新しく見つけた回数」だけ数えたいので、外側のループでだけ インクリメントします。3 つ目は無向グラフなのに片方向しかエッジを張らないと、片側からは辿れず別成分扱いになります。

やってみよう

n=6, edges=[[0,1],[1,2],[3,4]] で 3 が返ることを確認する (孤立 5)。
完全に連結なグラフは 1、エッジゼロなら n 個の成分になるはず。
本問題のあとに Union-Find で同じ問題を解いてみると、グラフ系の引き出しが増える (第 7 章で扱う)。

連結成分数を見たら DFS か Union-Find。両方書けるようになろう。

よくある質問

Q. DFS は再帰と反復どちらが良いですか？

A. コードの読みやすさは再帰、深さが極端に大きいケースでは反復（スタック使用）が安全です。Python は再帰深さ制限が 1000 のデフォルトなので、グラフ探索では sys.setrecursionlimit を上げるか反復に切り替えます。

Q. DFS の応用例は何がありますか？

A. 連結成分の検出、トポロジカルソート、サイクル検出、強連結成分分解（Tarjan / Kosaraju）など多数あります。バックトラッキング（数独・N クイーン）も DFS の応用で、解の探索と戻りを再帰で表現します。

Q. DFS と BFS の計算量は同じですか？

A. どちらも O(V + E)（V: 頂点数、E: 辺数）で同じです。違いは順序とメモリ使用パターンで、BFS は最大幅、DFS は最大深さに比例したメモリを使います。グラフの形状によってどちらが省メモリかは変わります。

次のレッスン

次は グラフのパス存在判定 で、BFS または DFS を使って、2 ノード間にパスが存在するかを真偽値で返す関数を実装する方法を学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

グラフ DFS の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. グラフ DFS とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

グラフ DFS で連結成分の数を数える