【JavaScript 算法】广度优先搜索：层层推进的搜索策略

/**
 * 广度优先搜索算法
 * @param {Object} graph - 图的邻接表表示
 * @param {string} start - 起始节点
 */
function breadthFirstSearch(graph, start) {
  const queue = [start]; // 初始化队列，将起始节点加入队列
  const visited = new Set(); // 用于记录已访问的节点

  visited.add(start); // 将起始节点标记为已访问

  while (queue.length > 0) {
    const node = queue.shift(); // 取出队列的头节点
    console.log(node); // 访问节点

    // 访问当前节点的所有相邻节点
    for (const neighbor of graph[node]) {
      // 如果相邻节点未被访问过，将其标记为已访问并加入队列
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

// 示例图的邻接表表示
const graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: [],
  E: ['F'],
  F: []
};

// 调用广度优先搜索算法
breadthFirstSearch(graph, 'A'); // 输出: A B C D E F

/**
 * 广度优先搜索算法（记录路径）
 * @param {Object} graph - 图的邻接表表示
 * @param {string} start - 起始节点
 * @return {Object} - 每个节点的路径
 */
function breadthFirstSearchWithPath(graph, start) {
  const queue = [[start]]; // 初始化队列，队列中存储路径
  const visited = new Set(); // 用于记录已访问的节点

  visited.add(start); // 将起始节点标记为已访问

  while (queue.length > 0) {
    const path = queue.shift(); // 取出队列的头路径
    const node = path[path.length - 1]; // 获取路径中的最后一个节点

    console.log(node); // 访问节点

    // 访问当前节点的所有相邻节点
    for (const neighbor of graph[node]) {
      // 如果相邻节点未被访问过，将其标记为已访问并加入队列
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        const newPath = [...path, neighbor]; // 创建新的路径
        queue.push(newPath); // 将新路径加入队列
      }
    }
  }
}

// 调用广度优先搜索算法（记录路径）
breadthFirstSearchWithPath(graph, 'A');