当前位置：首页 > JavaScript

js实现bfs

2026-03-13 22:39:40JavaScript

实现BFS的基本概念

BFS（广度优先搜索）是一种用于遍历或搜索树或图的算法。它从根节点开始，逐层访问所有相邻节点，确保先访问所有相邻节点后再进入下一层。

使用队列实现BFS

BFS通常使用队列来管理待访问的节点。队列的先进先出特性确保节点按照层级顺序被处理。

function bfs(graph, startNode) {
    const visited = new Set();
    const queue = [startNode];
    visited.add(startNode);

    while (queue.length > 0) {
        const currentNode = queue.shift();
        console.log(currentNode); // 处理当前节点

        for (const neighbor of graph[currentNode]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
}

示例图的表示

图可以用邻接表的形式表示，例如：

const graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
};

调用BFS函数

传入图结构和起始节点，即可执行BFS遍历：

bfs(graph, 'A');

处理有向图或无向图

上述代码适用于无向图。对于有向图，邻接表的构建方式会有所不同，但BFS的实现逻辑不变。

记录路径信息

如果需要记录从起始节点到其他节点的路径，可以修改BFS函数：

function bfsWithPath(graph, startNode) {
    const visited = new Set();
    const queue = [startNode];
    const paths = { [startNode]: [startNode] };
    visited.add(startNode);

    while (queue.length > 0) {
        const currentNode = queue.shift();

        for (const neighbor of graph[currentNode]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                paths[neighbor] = [...paths[currentNode], neighbor];
                queue.push(neighbor);
            }
        }
    }
    return paths;
}