Node.js广度优先搜索遍历图时console.log('found it!')未输出问题排查

问题排查结果 #

你的代码存在两个核心问题，导致无法触发打印逻辑：

1. 目标机场名称拼写错误
   你在airports数组中定义的曼谷机场代码是BKK，但BFS判断条件里写的是BKKK，多了1个字母K，永远不可能匹配到对应节点，自然不会打印found it!。
2. BFS遍历逻辑存在缺陷
   你当前的代码只有当节点匹配到BKKK的时候才会将其加入已访问集合和队列，其余所有未访问的相邻节点都不会入队，相当于整个遍历流程只能走第一层起始节点的相邻节点，后续层级完全无法遍历到。就算你把拼写改对，从PHX到BKK需要至少3跳，遍历根本走不到BKK所在的层级。

修复后的参考代码 #

const airports = 'PHX BKK OKC JFK LAX MEX EZE HEL LOS LAP LIM'.split(' ');

const routes = [
  ['PHX','LAX'],
  ['PHX','JFK'],
  ['JFK','OKC'],
  ['JFK','HEL'],
  ['JFK','LOS'],
  ['MEX','LAX'],
  ['MEX','BKK'],
  ['MEX','LIM'],
  ['MEX','EZE'],
  ['LIM','BKK'],
];

// 图结构
const adjacencyList = new Map();

// 添加节点
function addNode(airport){
  adjacencyList.set(airport, []);
}

// 添加无向边
function addEdge(origin,destination){
  adjacencyList.get(origin).push(destination);
  adjacencyList.get(destination).push(origin);
}

// 初始化图
airports.forEach(addNode);
routes.forEach(route => addEdge(...route));

// 修复后的BFS
function bfs(start, target){
  const visited = new Set();
  const queue = [start];
  visited.add(start); // 起始节点先标记为已访问

  while (queue.length > 0) {
    const airport = queue.shift();
    // 先判断当前节点是不是目标
    if(airport === target){
      console.log('found it!');
      // 返回目标机场的所有关联航线
      return adjacencyList.get(airport);
    }
    const destinations = adjacencyList.get(airport);
    // 所有未访问的相邻节点都要入队，才能完成全遍历
    for(const destination of destinations){
      if(!visited.has(destination)){
        visited.add(destination);
        queue.push(destination);
      }
    }
  }
  return null; // 没找到目标返回空
}

// 调用时传入正确的目标机场代码BKK
console.log(bfs('PHX', 'BKK'));

内容的提问来源于stack exchange，提问作者Carolyn Cordeiro