介绍下深度优先遍历和广度优先遍历，如何实现？

参考答案：

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

深度优先遍历（DFS）

描述：

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

实现方式：

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

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

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);
    }
  }
}

题目要点：

• 深度优先遍历（DFS）：

  • 策略：尽可能深入到每个分支的末端。
  • 实现：递归或栈。
  • 适用场景：适用于需要处理深层嵌套的场景，如解决迷宫问题。

• 广度优先遍历（BFS）：

  • 策略：逐层遍历，优先访问同一层的节点。
  • 实现：队列。
  • 适用场景：适用于找到最短路径或处理层次结构的场景，如寻找最短路径问题。