dfs js实现

DFS（深度优先搜索）的 JavaScript 实现

深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。以下是几种常见的实现方式：

递归实现（适用于树或图）

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

  visited.add(node);
  console.log(node.value); // 处理当前节点

  // 遍历相邻节点
  node.neighbors.forEach(neighbor => {
    dfs(neighbor, visited);
  });
}

迭代实现（使用栈）

function dfs(startNode) {
  const stack = [startNode];
  const visited = new Set();

  while (stack.length) {
    const node = stack.pop();

    if (!visited.has(node)) {
      visited.add(node);
      console.log(node.value); // 处理当前节点

      // 将相邻节点逆序压入栈中（保持遍历顺序）
      [...node.neighbors].reverse().forEach(neighbor => {
        stack.push(neighbor);
      });
    }
  }
}

针对二叉树的实现

// 递归版
function dfsBinaryTree(node) {
  if (!node) return;

  console.log(node.val); // 前序遍历
  dfsBinaryTree(node.left);
  dfsBinaryTree(node.right);
}

// 迭代版
function dfsBinaryTreeIterative(root) {
  const stack = [root];

  while (stack.length) {
    const node = stack.pop();
    if (!node) continue;

    console.log(node.val);
    stack.push(node.right); // 右节点先入栈
    stack.push(node.left);  // 左节点后入栈
  }
}

图遍历注意事项

对于图结构的DFS，必须使用visited集合来避免循环访问：

function graphDFS(startNode) {
  const stack = [startNode];
  const visited = new Set([startNode]);

  while (stack.length) {
    const node = stack.pop();
    console.log(node.value);

    node.neighbors.forEach(neighbor => {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        stack.push(neighbor);
      }
    });
  }
}

这些实现可以根据具体需求进行调整，例如添加回调函数来处理节点，或返回遍历结果数组。