深度优先和广度优先

把大学的东西拿回来复习复习，记录一下深度优先和广度优先的写法

深度优先遍历

尽可能的往深处的搜索图的分支需要深入地搜索，或者需要找到所有可能的解，应该使用 DFS，例如：寻找连通性，寻找所有问题的解等

实现思路：

确定一个根节点
对根节点的没访问过的相邻节点进行深度优先遍历

代码实现：

递归实现

JS

function depthFirstSearch(node) {
  if (node == null) {
      return;
  }

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

  // 遍历节点的所有子节点
  for (let i = 0; i < node.children.length; i++) {
      depthFirstSearch(node.children[i]);
  }
}

栈实现

JS

function depthFirstSearch(root) {
  let stack = [];
  stack.push(root);

  while (stack.length > 0) {
      let node = stack.pop();
      console.log(node.value); // 访问当前节点

      // 将节点的子节点添加到栈中
      for (let i = node.children.length - 1; i >= 0; i--) {
          stack.push(node.children[i]);
      }
  }
}

广度优先遍历

需要找到从源节点到目标节点的最短路径，或者需要广泛地搜索，那么应该使用 BFS，例如：无权图的最短路径、寻找所有邻居等

实现思路：

从根节点开始，然后遍历所有相邻的节点
对每个相邻节点，再遍历它们的相邻节点

代码实现：

队列实现

JS

  function breadthFirstSearch(root) {
  let queue = [];
  queue.push(root);

  while (queue.length > 0) {
      let node = queue.shift();
      console.log(node.value); // 访问当前节点

      // 将节点的子节点添加到队列中
      for (let i = 0; i < node.children.length; i++) {
         queue.push(node.children[i]);
    }
  }
}

LeetCode 相关题目

深度优先遍历（DFS）的题目：
广度优先遍历（BFS）的题目：