幅優先探索（BFS）

幅優先探索を使用するタイミング

BFSはノードを層ごとに探索する必要があるとき、または重みなしグラフで最短経路を見つける必要があるときに使用します。最も一般的にはレベル順走査に使用されますが、以下にも適応できます：

レベル順ツリー走査（クラシックなユースケース）
重みなしグラフの最短経路（層ごとの探索により最適解が保証される）
開始点から距離kにあるすべてのノードを見つける
グラフが二部グラフかチェック（同じグループ内の2つのノードが接続されていない2つのグループにノードを分割できる - 交互の層でノードを着色することで行う）
Webクローリング（より深く進む前に同じ深さのリンクを探索）
ソーシャルネットワーク分析（n次の分離度内の接続を見つける）
現在の「距離」でのすべての可能性を探索してから、さらに先に進む必要がある問題

例題

会社組織図：ツリーとして表される会社階層が与えられたとき、報告構造を理解するために全従業員をレベルごとに出力します。

        CEO
       /   \
     CTO   CFO
    /  \     \
  Dev1 Dev2  Acc1

Level 0: CEO
Level 1: CTO, CFO
Level 2: Dev1, Dev2, Acc1

これは管理層を明確に示しています - まずCEOへのすべての直接報告者、次にそのすべての直接報告者、というように続きます。

最も重要な洞察

BFSは距離d+1のどのノードよりも前に、距離dのすべてのノードを探索する - そしてキュー（FIFO）を使用することで、ノードが発見された正確な順序で処理されることが保証され、これが自動的にレベルごとの探索と重みなしグラフでの最短経路を提供します。

メンタルノート：アルゴリズムの天才性はキューのFIFO特性にあります。ノードの隣接ノードを発見すると、それらはキューの後ろに行きます。これは、現在のレベルのすべてのノードが次のレベルのどのノードよりも前に処理されることを意味します。劇場を列ごとに埋めていくようなものです - 2列目が完全に満たされるまで3列目を開始することはできません。

決定フレームワーク

すべてのノードで、1つの簡単な決定に直面します：

現在のノードを処理する（訪問済みとしてマーク）
すべての未訪問の隣接ノードを将来の探索のためにキューに追加

キューが順序を強制します - いつノードを処理するかを決定するのはあなたではなく、FIFO構造がそれを行います。

コード

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function bfs(root) {
  // 空のツリーを処理
  if (root == null) {
    return;
  }

  // ルートノードでキューを初期化
  const queue = [root];
  let level = 0;

  // ノードをレベルごとに処理
  while (queue.length > 0) {
    // 現在のレベルサイズをキャプチャ - これが鍵！
    const levelSize = queue.length;
    const currentLevelNodes = [];

    // 現在のレベルのすべてのノードを処理
    for (let i = 0; i < levelSize; i++) {
      // 決定フレームワーク：現在のノードを処理
      const currentNode = queue.shift();
      currentLevelNodes.push(currentNode.val);

      // 決定フレームワーク：未訪問の隣接ノード（子）をキューに追加
      if (currentNode.left != null) {
        queue.push(currentNode.left);
      }
      if (currentNode.right != null) {
        queue.push(currentNode.right);
      }
    }

    // 現在のレベルを出力
    console.log(`Level ${level}: ${currentLevelNodes.join(", ")}`);
    level++;
  }
}

// 会社組織図での使用例
const ceo = new TreeNode("CEO");
const cto = new TreeNode("CTO");
const cfo = new TreeNode("CFO");
const dev1 = new TreeNode("Dev1");
const dev2 = new TreeNode("Dev2");
const acc1 = new TreeNode("Acc1");

ceo.left = cto;
ceo.right = cfo;
cto.left = dev1;
cto.right = dev2;
cfo.right = acc1;

bfs(ceo);
// 出力：
// Level 0: CEO
// Level 1: CTO, CFO
// Level 2: Dev1, Dev2, Acc1

疑問解消

よくある疑問：「なぜDFS（深さ優先探索）を使ってツリーを走査できないのか？結局すべてのノードを訪問するのではないか？レベル順走査でBFSが特別な理由は何か？」

これは自然な疑問です。なぜならBFSとDFSの両方がすべてのノードを訪問するからです。特定の問題でBFSが不可欠な理由を見てみましょう。

DFSでもうまくいくと思うかもしれない理由

会社組織図を考えてください。DFSで、次のように考えるかもしれません：

「まず深く進む：CEO → CTO → Dev1、それからバックトラック」
「最終的にすべてのノードを訪問するので、違いは何か？」
「深さを追跡して、レベルごとにノードをグループ化することはできないか？」

この考え方が重要なポイントを見逃している理由

重要な認識：BFSは単にすべてのノードを訪問するだけではありません - ユニークな保証を提供する特定の順序でそれらを訪問します！

BFS対DFSの走査順序を比較してみましょう：

BFS順序：CEO → CTO → CFO → Dev1 → Dev2 → Acc1
（レベル0のすべて、次にレベル1のすべて、次にレベル2のすべて）

DFS順序：CEO → CTO → Dev1 → Dev2 → CFO → Acc1
（まず深く進み、レベル間をジャンプ）

具体例：最短経路の発見

重みなしグラフでCEOからAcc1への最短経路を見つけることを想像してください：

BFSの場合：

ステップ1：CEOを処理（距離0）
ステップ2：CTO、CFOを処理（距離1） - CFOを発見！
ステップ3：CFOの子を処理 - 距離2でAcc1を発見！

DFSの場合（より長い経路を取る可能性がある）：

ステップ1：CEOを処理
ステップ2：CTOを処理（左に進む）
ステップ3：Dev1を処理（さらに左に深く進む）
ステップ4：CTOにバックトラック
ステップ5：Dev2を処理
ステップ6：CEOまでずっとバックトラック
ステップ7：最後にCFOを処理
ステップ8：Acc1を処理

DFSはノードを見つけるかもしれませんが、それが最短経路経由であることは保証しません！

なぜキューが不可欠なのか

BFSのキューは「世代トラッカー」のように機能します：

世代0（ルート）：キューにCEOのみ
世代1（子）：CTOとCFOがキューに追加
世代2（孫）：Dev1、Dev2、Acc1がキューに追加

FIFO特性により以下が保証されます：

すべての世代1ノードがどの世代2ノードよりも前に処理される
これはDFSのスタック（LIFO）や再帰呼び出しスタックでは不可能

レベルサイズトリック

レベルごとの処理を可能にするBFSの重要な行：

const levelSize = queue.length; // 現在のレベルのサイズのスナップショット

これは現在のレベルにいくつのノードがあるかを正確にキャプチャします。処理中にキューに新しいノードを追加していても、1つのレベルがどこで終わり、次がどこで始まるかを正確に知っています。

これが正確性を保証する理由：

レベルの処理を開始するとき、キューにはそのレベルのノードのみが含まれている
各ノードを処理するとき、その子（次のレベル）をキューに追加
しかし、levelSizeノードのみを処理するので、現在のレベルが完了したときに正確に停止
キューには次のレベルのノードのみが含まれるようになる

このエレガントなメカニズムにより、BFSはレベル順走査と最短経路を保証できます。これは深さ優先の性質により、DFSが根本的に提供できないものです。