实现BFS函数无法遍历顶点0的问题排查求助

核心错误分析 #

你的代码存在两个致命逻辑错误，直接导致BFS遍历异常，无法访问到顶点0：

• 错误使用遍历节点：在while循环中，你已经将节点出队到deq变量，但遍历邻接表时却始终用graph[source]，而不是当前出队的节点deq的邻接表graph[deq]。这意味着你根本没有处理每个出队节点的邻接节点，而是一直在操作初始source或者被错误修改后的source的邻接表。

• 非法修改source变量：在遍历邻接节点的过程中，你错误地将source = el，这直接改变了后续遍历的基准节点，导致BFS的层级遍历逻辑完全混乱。BFS的核心是按层级处理每个节点的所有邻接节点，而不是随意切换遍历的基准节点。

以调用doBFS(adjList, 3)为例，初始source是3，出队后本该遍历3的邻接节点2和6，但你的代码在处理第一个邻接节点2时，把source改成了2，后续循环就开始遍历2的邻接节点，完全跳过了3的另一个邻接节点6的正常处理，后续的遍历顺序彻底偏离了BFS的正确路径，自然无法到达与3连通的顶点0（路径是3→2→4→1→0）。

修正后的代码 #

var doBFS = function(graph, source) {
    var bfsInfo = [];

    for (var i = 0; i < graph.length; i++) {
        bfsInfo[i] = {
            distance: null,
            predecessor: null
        };
    }

    bfsInfo[source].distance = 0;

    var queue = new Queue();
    queue.enqueue(source);

    // Traverse the graph
    while(!queue.isEmpty()){
        var current = queue.dequeue(); // 用current表示当前处理的节点

        // 遍历当前节点的所有邻接节点，而不是source的
        for(var j = 0; j < graph[current].length; j++){
            var neighbor = graph[current][j];

            if (bfsInfo[neighbor].distance === null){
                bfsInfo[neighbor].distance = bfsInfo[current].distance + 1;
                bfsInfo[neighbor].predecessor = current;
                queue.enqueue(neighbor);
            }
        }
    }
    
    return bfsInfo;
};

修正说明 #

• 把出队节点重命名为current，明确表示当前正在处理的节点
• 遍历graph[current]（当前节点的邻接表），替代原代码中错误的graph[source]
• 移除了对source变量的修改，避免破坏BFS的遍历逻辑
• 对未访问的邻接节点，基于当前节点current的距离计算新距离，设置前驱为current后入队

修正后调用doBFS(adjList, 3)，顶点0的distance会被正确设置为4，predecessor为1，符合BFS的遍历预期。

内容的提问来源于stack exchange，提问作者Ruiyot Abby