JavaScriptで学ぶ幅優先探索（BFS）トラバーサルの仕組みと実装方法

BFS（幅優先探索）は、子ノードへ進む前に隣接する頂点を先に訪問するグラフ探索アルゴリズムです。探索の過程では「キュー」というデータ構造を使用するのが特徴です。

BFSの基本的な手順

BFSは以下のルールに従って動作します。

• 隣接する未訪問の頂点を訪問し、「訪問済み」としてマークします。その頂点を表示し、キューに追加します。
• 未訪問の隣接頂点が存在しない場合は、キューの先頭から頂点を取り出します（デキュー）。
• キューが空になるまで、上記のルール1とルール2を繰り返します。

BFSトラバーサルの流れ（図解）

実際のBFSトラバーサルがどのように進むのか、ステップごとに見ていきましょう。

ステップ	トラバーサル	説明
1		キューを初期化します。
2		開始ノードである S を訪問し、訪問済みとしてマークします。
3		S の未訪問の隣接ノードを確認します。この例では3つのノードがありますが、アルファベット順に A を選択し、訪問済みとしてマークしてキューに追加します。
4		次に、S の未訪問の隣接ノードは B です。訪問済みとしてマークし、キューに追加します。
5		次に、S の未訪問の隣接ノードは C です。こちらも訪問済みとしてマークし、キューに追加します。
6		これで S には未訪問の隣接ノードがなくなりました。そこでデキューを行うと、A が取り出されます。
7		A からは D が未訪問の隣接ノードとして見つかります。D を訪問済みとしてマークし、キューに追加します。

この時点で、未訪問（未マーク）のノードは残っていません。ただし、アルゴリズムの規則に従い、すべてのノードを確実に処理し終えるまでデキューを続けます。キューが完全に空になった時点で、プログラムは終了となります。

JavaScriptでのBFS実装

それでは、このBFSをJavaScriptでどのように実装できるのか見ていきましょう。

BFS(node) {
    // キューを作成し、初期ノードを追加する
    let q = new Queue(this.nodes.length);
    let explored = new Set();
    q.enqueue(node);

    // 最初のノードを探索済みとしてマークする
    explored.add(node);

    // キューが空になるまで処理を続ける
    while (!q.isEmpty()) {
        let t = q.dequeue();

        // キューから取り出された要素をログに出力
        console.log(t);

        // 1. edgesオブジェクトから、このノードが直接接続しているノードを検索する。
        // 2. すでに探索済みのノードをフィルタリングして除外する。
        // 3. 未探索の各ノードを探索済みとしてマークし、キューに追加する。
        this.edges[t]
        .filter(n => !explored.has(n))
        .forEach(n => {
            explored.add(n);
            q.enqueue(n);
        });
    }
}

この実装のポイントは、探索済みノードの管理にSetオブジェクトを使っている点です。Setにより、あるノードが既に訪問されたかどうかを効率的に判定でき、同じノードが何度もキューに入ることを防げます。

コードのテスト

この関数は、以下のようなグラフを使ってテストできます。

let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");

g.addEdge("A", "C");
g.addEdge("A", "B");
g.addEdge("A", "D");
g.addEdge("D", "E");
g.addEdge("E", "F");
g.addEdge("B", "G");

g.BFS("A");

出力結果

このコードを実行すると、以下の出力が得られます。

A
C
B
D
G
E
F

まとめ

幅優先探索（BFS）は、開始ノードから近い順にノードを訪問するシンプルながら強力なアルゴリズムです。キューによる「先入れ先出し（FIFO）」の性質を利用することで、グラフを層状に探索できます。最短経路の探索やソーシャルネットワークの分析など、さまざまな場面で活用されるため、ぜひ実装方法をマスターしておきましょう。なお、BFSの計算量は頂点数をV、辺数をEとした場合に O(V + E) となり、非常に効率的な探索手法です。