JS实现dfs

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

递归实现

function dfsRecursive(node, visited = new Set()) {
  if (!node || visited.has(node)) return;
  visited.add(node);
  console.log(node.value); // 处理当前节点
  node.children.forEach(child => dfsRecursive(child, visited));
}

迭代实现（使用栈）

function dfsIterative(root) {
  const stack = [root];
  const visited = new Set();
  while (stack.length) {
    const node = stack.pop();
    if (!node || visited.has(node)) continue;
    visited.add(node);
    console.log(node.value); // 处理当前节点
    // 子节点逆序入栈以保证顺序
    [...node.children].reverse().forEach(child => stack.push(child));
  }
}

使用场景示例

树结构遍历

class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }
}

// 构建树
const root = new TreeNode(1);
root.children = [new TreeNode(2), new TreeNode(3)];
root.children[0].children = [new TreeNode(4), new TreeNode(5)];

图结构遍历（需处理环）

function dfsGraph(node, graph, visited = new Set()) {
  visited.add(node);
  console.log(node);
  graph[node].forEach(neighbor => {
    if (!visited.has(neighbor)) dfsGraph(neighbor, graph, visited);
  });
}

const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D'],
  'C': ['A', 'E'],
  'D': ['B'],
  'E': ['C']
};

复杂度分析

• 时间复杂度：O(V + E)（V为顶点数，E为边数）
• 空间复杂度：O(V)（最坏情况下栈/递归深度）

注意事项

• 处理图结构时必须记录已访问节点，避免循环导致的无限递归
• 递归实现可能因调用栈过深导致堆栈溢出，大型数据结构建议使用迭代实现
• 可根据实际需求修改处理节点的逻辑（如替换console.log）