求助：实现无需指定终点的非二叉树BFS遍历函数

一、修改实现完整的BFS遍历 #

你的当前代码因为加入了终点判断逻辑，导致无法完成全图遍历，同时visited数组没有正确记录所有访问过的节点。以下是调整后的代码，满足输入图对象，返回从左到右的广度优先遍历节点数组的需求：

const bfs = (graph, start = Object.keys(graph)[0]) => {
  // 初始化队列，起始节点默认取图的第一个键
  const queue = [start];
  // 存储遍历结果的数组
  const visited = [start];

  while (queue.length > 0) {
    // 取出队列头部节点（FIFO特性保证广度优先）
    const currentNode = queue.shift();
    // 处理节点无子孙的情况，默认空数组
    const children = graph[currentNode] || [];
    
    // 按数组索引顺序遍历子节点，加入队列和结果数组
    for (const child of children) {
      // 如果你的图可能存在环，需要添加以下判断避免重复访问
      // if (!visited.includes(child)) {
        visited.push(child);
        queue.push(child);
      // }
    }
  }

  return visited;
};

代码说明： #

1. 参数调整：去掉不必要的end参数，start设为可选，默认取图的第一个节点
2. 队列操作：使用shift()取出队首节点（符合BFS的先进先出规则），子节点按顺序push到队尾，保证从左到右的遍历顺序
3. 结果记录：每访问一个子节点就加入visited数组，最终返回完整的遍历序列
4. 环处理：如果你的图可能存在循环引用，取消注释判断条件，避免重复处理同一节点

测试调用：

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

bfs(graph); // 返回 ['A', 'B', 'C', 'D', 'E', 'F', 'G']

二、BFS记录最短路径 #

BFS天然适合找无权图的最短路径，因为它按层遍历，第一次到达目标节点的路径就是最短路径。下面是实现代码，通过记录节点的前驱来回溯路径：

const findShortestPath = (graph, start = Object.keys(graph)[0], end) => {
  // 边界判断：起始或目标节点不存在
  if (!graph[start] || !graph[end]) return [];

  const queue = [start];
  // 记录每个节点的前驱节点，用于回溯路径
  const predecessors = { [start]: null };

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

    // 找到目标节点，提前终止遍历
    if (currentNode === end) break;

    const children = graph[currentNode] || [];
    for (const child of children) {
      // 未访问过的节点才记录前驱
      if (!predecessors.hasOwnProperty(child)) {
        predecessors[child] = currentNode;
        queue.push(child);
      }
    }
  }

  // 目标节点不可达，返回空数组
  if (!predecessors.hasOwnProperty(end)) return [];

  // 从目标节点回溯到起始节点
  const path = [];
  let current = end;
  while (current !== null) {
    path.push(current);
    current = predecessors[current];
  }

  // 反转得到从起始到目标的路径
  return path.reverse();
};

代码说明： #

1. 前驱记录：用predecessors对象存储每个节点的上一级节点，比如E的前驱是B，B的前驱是A
2. 路径回溯：找到目标节点后，从end开始反向遍历前驱，最后反转数组得到正序的最短路径
3. 边界处理：判断节点是否存在、是否可达，避免报错

测试调用：

findShortestPath(graph, 'A', 'E'); // 返回 ['A', 'B', 'E']
findShortestPath(graph, 'A', 'G'); // 返回 ['A', 'C', 'G']

三、你的原代码问题总结 #

1. 多余的end参数和判断逻辑，导致遍历提前终止，无法完成全图遍历
2. visited数组仅初始化了起始节点，后续未将子节点加入，导致结果缺失
3. 队列合并方式queue = [...queue, ...graph[node]]虽然可行，但循环push更直观，也便于处理有环的场景

内容的提问来源于stack exchange，提问作者Данил Побирский