# 队列和广度优先搜索(BFS)

广度优先搜索（BFS）的一个常见应用是找出从根结点到目标结点的最短路径。

BFS 从根节点开始，每轮将一层节点加入队列，并在下一轮移除队列。
如果在第 k 轮中将结点 X 添加到队列中，则根结点与 X 之间的最短路径的长度恰好是 k。也就是说，第一次找到目标结点时，你已经处于最短路径中。
结点的处理顺序与它们添加到队列的顺序是完全相同的顺序，即先进先出（FIFO）。这就是我们在 BFS 中使用队列的原因。

function BFS(root, target) {
  if (!root) {
    return;
  }
  let step = 0;
  let set = new Set();
  let list = Array.isArray(root) ? root : [root];
  while (list.length) {
    step++;
    let len = list.length;
    for (let i = 0; i < len; i++) {
      let cur = list[0];
      if (cur.id === target) {
        return step;
      }
      if (cur.children) {
        for (let j = 0, childLen = cur.children.length; j < childLen; j++) {
          let curChildren = cur.children[j];
          if (!set.has(curChildren)) {
            set.add(curChildren);
            list.push(curChildren);
          }
        }
      }
      list.shift();
    }
  }
  return -1;
}
const nodeE = { id: 'e' };
const nodeG = { id: 'g' };
const data = {
  id: 'a',
  children: [
    { id: 'b', children: [nodeE] },
    { id: 'c', children: [nodeE, { id: 'f', children: [nodeG] }] },
    { id: 'd', children: [nodeG] }
  ]
};
// debugger;
console.log(BFS(data, 'g')); // 3

← 队列栈 →