モダンJavaScript入門: 幅優先探索(BFS)を使用したグラフ探索

1. 幅優先探索(BFS)とは

幅優先探索（BFS: Breadth-First Search）は、グラフの探索アルゴリズムの一つで、根から近いノードを優先的に探索する方法です。キューというデータ構造を用いて実装することが一般的です。

2. BFSのアルゴリズムとコード例

BFSの基本的なアルゴリズムは以下の通りです。

初期ノードをキューに追加する。
キューが空になるまで以下の操作を繰り返す。
1. キューからノードを一つ取り出す（dequeue）。
2. そのノードが目的のノードなら探索を終了する。
3. そうでなければ、そのノードの隣接ノードのうち未探索のものを全てキューに追加する。

JavaScriptによるBFSのコード例は以下の通りです。

class Graph {
    constructor(nodes) {
        this.nodes = nodes;
        this.adjList = new Map();
        nodes.forEach(node => this.adjList.set(node, []));
    }

    addEdge(node1, node2) {
        this.adjList.get(node1).push(node2);
        this.adjList.get(node2).push(node1);
    }

    bfs(startNode) {
        const visited = new Set();
        const queue = [startNode];

        while (queue.length > 0) {
            const node = queue.shift();
            if (!visited.has(node)) {
                console.log(node);
                visited.add(node);
                queue.push(...this.adjList.get(node));
            }
        }
    }
}

const g = new Graph(['A', 'B', 'C', 'D', 'E', 'F']);
g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
g.addEdge('B', 'E');
g.addEdge('C', 'F');
g.bfs('A');  // or any node

3. BFSの応用例

BFSは様々な問題に応用できます。ここでは、最短経路探索、連結成分の検出、二部グラフ判定の3つを例に挙げます。

3.1 最短経路探索

BFSは最短経路を見つけるのにも使われます。ここでは、グラフ上での最短経路を見つける例を示します。

class Graph {
    constructor(nodes) {
        this.nodes = nodes;
        this.adjList = new Map();
        nodes.forEach(node => this.adjList.set(node, []));
    }

    addEdge(node1, node2) {
        this.adjList.get(node1).push(node2);
        this.adjList.get(node2).push(node1);
    }

    shortestPath(startNode, endNode) {
        const visited = new Set();
        const queue = [[startNode, []]];

        while (queue.length > 0) {
            const [node, path] = queue.shift();
            if (node === endNode) {
                return [...path, node];
            }

            if (!visited.has(node)) {
                visited.add(node);
                const neighbors = this.adjList.get(node);
                for (const neighbor of neighbors) {
                    queue.push([neighbor, [...path, node]]);
                }
            }
        }

        return null;
    }
}

const g = new Graph(['A', 'B', 'C', 'D', 'E', 'F']);
g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
g.addEdge('B', 'E');
g.addEdge('C', 'F');
console.log(g.shortestPath('A', 'F'));  // ['A', 'C', 'F']

3.2 連結成分の検出

グラフがいくつの連結成分に分かれているかを見つけるのにBFSを使うことができます。

class Graph {
    constructor(nodes) {
        this.nodes = nodes;
        this.adjList = new Map();
        nodes.forEach(node => this.adjList.set(node, []));
    }

    addEdge(node1, node2) {
        this.adjList.get(node1).push(node2);
        this.adjList.get(node2).push(node1);
    }

    bfs(startNode) {
        const visited = new Set();
        const queue = [startNode];
        while (queue.length > 0) {
            const node = queue.shift();
            visited.add(node);
            for (const neighbor of this.adjList.get(node)) {
                if (!visited.has(neighbor)) {
                    queue.push(neighbor);
                }
            }
        }
        return visited;
    }

    getConnectedComponents() {
        const visited = new Set();
        const components = [];
        for (const node of this.nodes) {
            if (!visited.has(node)) {
                const component = this.bfs(node);
                components.push(component);
                for (const node of component) {
                    visited.add(node);
                }
            }
        }
        return components;
    }
}

const g = new Graph(['A', 'B', 'C', 'D', 'E', 'F', 'G']);
g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('D', 'E');
g.addEdge('F', 'G');
console.log(g.getConnectedComponents());  // [Set {'A', 'B', 'C'}, Set {'D', 'E'}, Set {'F', 'G'}]

3.3 二部グラフ判定

BFSは二部グラフを判定するのにも使われます。

class Graph {
    constructor(nodes) {
        this.nodes = nodes;
        this.adjList = new Map();
        nodes.forEach(node => this.adjList.set(node, []));
    }

    addEdge(node1, node2) {
        this.adjList.get(node1).push(node2);
        this.adjList.get(node2).push(node1);
    }

    isBipartite() {
        const color = {};
        for (const node of this.nodes) {
            if (!(node in color)) {
                color[node] = 0;
                const queue = [node];
                while (queue.length > 0) {
                    const node = queue.shift();
                    for (const neighbor of this.adjList.get(node)) {
                        if (!(neighbor in color)) {
                            color[neighbor] = 1 - color[node];
                            queue.push(neighbor);
                        } else if (color[neighbor] === color[node]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}

const g = new Graph(['A', 'B', 'C', 'D']);
g.addEdge('A', 'B');
g.addEdge('B', 'C');
g.addEdge('C', 'D');
g.addEdge('D', 'A');
console.log(g.isBipartite());  // true

以上、幅優先探索(BFS)を使用したグラフ探索の基本的な理解と応用例について学びました。これからBFSを用いた様々な問題解決にチャレンジしてみてください。

AIko Code Symphony