前端面试题：介绍下深度优先遍历和广度优先遍历，如何实现？

大叔爱吃猕猴桃

深度优先遍历（DFS）和广度优先遍历（BFS）是两种常见的图或树的遍历算法。它们用于遍历和搜索图或树的数据结构。下面是对这两种遍历算法的详细介绍和实现方法。

深度优先遍历（DFS）

描述：

深度优先遍历 是一种优先深入到树或图的深层节点的遍历策略。它尽可能深入到每一个分支的末端，然后回溯到上一层继续遍历。

实现方式：

递归实现：
- 使用递归函数遍历每个节点。
栈实现：
- 使用栈来模拟递归过程，手动维护节点的遍历状态。

递归实现示例（以树为例）：

function dfsRecursive(node, visited = new Set()) {
  if (!node || visited.has(node.value)) return;

  // 访问当前节点
  console.log(node.value);
  visited.add(node.value);

  // 遍历所有子节点
  for (let child of node.children) {
    dfsRecursive(child, visited);
  }
}

栈实现示例（以树为例）：

function dfsStack(root) {
  const stack = [root];
  const visited = new Set();

  while (stack.length > 0) {
    const node = stack.pop();
    if (!node || visited.has(node.value)) continue;

    // 访问当前节点
    console.log(node.value);
    visited.add(node.value);

    // 将子节点加入栈
    for (let child of node.children) {
      stack.push(child);
    }
  }
}

广度优先遍历（BFS）

描述：

广度优先遍历 是一种优先遍历树或图的所有相邻节点的遍历策略。它从根节点开始，逐层向外扩展，访问所有同一层的节点，然后再向下一层扩展。

实现方式：

使用队列来存储待访问的节点，保证节点按照层次的顺序被访问。

实现示例（以树为例）：

function bfs(root) {
  const queue = [root];
  const visited = new Set();

  while (queue.length > 0) {
    const node = queue.shift();
    if (!node || visited.has(node.value)) continue;

    // 访问当前节点
    console.log(node.value);
    visited.add(node.value);

    // 将子节点加入队列
    for (let child of node.children) {
      queue.push(child);
    }
  }
}