グラフ BFS で連結成分サイズを求める｜コードで実践

グラフ BFS で連結成分サイズを求める

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

BFS の本質は「キュー (FIFO)」

走査ではどちらでも構いませんが、adj の方がノード v の隣接を O(1) で取り出せて速いです

グラフ はノード (頂点) とエッジ (辺) からなるデータ構造で、SNS の友達関係、地図の道路網、Web のリンク構造、依存関係グラフなど、実世界のさまざまな関係を表現できます

グラフ BFS で連結成分サイズを求めるとは

幅優先探索 (BFS) を使って、指定した頂点を含む連結成分のノード数を返す関数を実装する。本レッスンでは、グラフ BFS で連結成分サイズを求めるの基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

グラフ はノード (頂点) とエッジ (辺) からなるデータ構造で、SNS の友達関係、地図の道路網、Web のリンク構造、依存関係グラフなど、実世界のさまざまな関係を表現できます。木は「親が 1 つしかないグラフ」とも言えるので、木で学んだ走査の発想がそのままグラフでも使えます。

ただしグラフには大きな違いが 2 つあります。1 つ目は サイクル が存在しうること。木は親から子へ一方向ですが、グラフは A -- B -- C -- A のようにループできます。2 つ目は 同じノードに複数経路で到達 しうること。何も対策せずに走査すると、同じノードを何度も訪問し無限ループになります。

グラフ走査の鉄則は 訪問済み集合 visited を用意して、同じノードを 2 度処理しないこと。これだけでサイクルも多重辺も怖くない。

グラフの表現方法

本コースではグラフを次の 2 通りで表します。

エッジリスト edges = [[0,1], [1,2], [2,0], ...]。サイズ m の配列。
隣接リスト (adjacency list) adj = {0: [1, 2], 1: [0], 2: [0]}。ノード ID から隣接ノードの配列へのマップ。

走査ではどちらでも構いませんが、adj の方がノード v の隣接を O(1) で取り出せて速いです。本問題でも内部でエッジリストを隣接リストに変換してから探索します。

diagram (will load when visible)

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

上の例は 5 ノード {0,1,2,3,4} のうち 0,1,2 が連結成分、3,4 がもう 1 つの連結成分です

上の例は 5 ノード {0,1,2,3,4} のうち 0,1,2 が連結成分、3,4 がもう 1 つの連結成分です。start=0 から BFS をすれば {0,1,2} の 3 つのノードが訪問でき、サイズは 3 と返ります。

BFS の流れ

BFS は キュー を使って「近いノードから順に」訪問するアルゴリズムです。距離が小さい順に展開していくので、後で扱う 最短経路問題 の基礎にもなります。

BFS の本質は「キュー (FIFO)」。先に入れた = 近いノードから先に処理される性質が、最短性の保証につながる。

キューに start を入れて visited に追加する
キューが空になるまで、先頭ノード u を取り出す
u の隣接ノード v のうち、visited でないものをキューに追加し visited に入れる
取り出した u の数 (= visited のサイズ) を返す

計算量は O(n + m) です (ノード数 n、エッジ数 m)。各ノード / エッジを定数回しか触らないため、グラフサイズに対して線形時間で動きます。

Python での実装

Python

from collections import deque

def bfsComponentSize(n, edges, start):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    visited = {start}
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in adj[u]:
            if v not in visited:
                visited.add(v)
                queue.append(v)
    return len(visited)

deque は両端から O(1) で出し入れできるキュー用のコンテナです。list.pop(0) だと O(n) になるので避けます。

JavaScript での実装

JavaScript

function bfsComponentSize(n, edges, start) {
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }
  const visited = new Set([start]);
  const queue = [start];
  let head = 0;
  while (head < queue.length) {
    const u = queue[head++];
    for (const v of adj[u]) {
      if (!visited.has(v)) {
        visited.add(v);
        queue.push(v);
      }
    }
  }
  return visited.size;
}

JS には専用 Queue がないので、head インデックスを進める運用で擬似的なキューにしています。shift() を使うと O(n) で遅いため、本格的なグラフではこの方法が無難です。

よくある間違い

1 つ目は visited をキューに入れる時ではなく取り出す時にマークしてしまうケースです。すると同じノードを複数回キューに入れてしまい、結果は合っても処理量が膨らみます。キューに入れる瞬間にマーク が定石。2 つ目は 無向グラフ なのに adj[a].append(b) 片方向しか追加しないケース。b -- a も使えるように両方向に追加します。3 つ目は start ノードを visited に入れ忘れて、最初のループで start を 2 度処理してしまう問題です。

やってみよう

n=5, edges=[[0,1],[1,2],[2,0],[3,4]], start=0 を試して 3 が返ることを確認する。
start=3 に変えると 2 が返るはず。確かめてみよう。
エッジを 1 つも持たない孤立ノード (n=1, edges=[], start=0) でも 1 が返ることを確認する。

BFS は最短経路の基礎。「距離が近いものから順に」訪問する規則を体に染み込ませよう。

よくある質問

Q. BFS と DFS はどう使い分けますか？

A. 最短経路（最小ステップ数）が欲しいなら BFS、全探索やバックトラックなら DFS が向きます。BFS は queue、DFS は stack や再帰で実装します。メモリ使用量はグラフの形状に依存します。横に広いグラフでは BFS のキュー（フロンティア）が大きくなり、縦に深いグラフでは DFS のスタックが深くなります。

Q. 重み付きグラフの最短経路は BFS で良いですか？

A. 辺の重みが全て同じなら BFS で十分です。異なる重みがあるならダイクストラ法（優先度付きキュー）を使ってください。負の重みを許すならベルマンフォード、全頂点ペアならフロイド-ワーシャル法と、用途で使い分けます。

Q. 訪問済みの管理はどうすれば良い？

A. Set や boolean[] で「訪れた」フラグを管理するのが定石です。BFS では queue に入れた時点でフラグを立てるのがコツで、取り出した時点で立てると同じノードが複数回 queue に入り処理が膨らみます。

次のレッスン

次は グラフ DFS で連結成分の数を数える で、深さ優先探索 (DFS) を使って、指定した頂点を含む連結成分の数を数える方法を学びます。

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

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

理解度チェック (30 秒)

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

この章のポイント

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

関連レッスン

グラフ BFS で連結成分サイズを求める