当前位置：首页 > JavaScript

JS实现dfs

2026-03-14 08:40:47JavaScript

深度优先搜索（DFS）实现

深度优先搜索是一种用于遍历或搜索树或图的算法。在JavaScript中，可以通过递归或栈来实现DFS。

递归实现

递归实现DFS是最直观的方法，适用于树或图的遍历。

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

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

  node.children.forEach(child => {
    dfs(child, visited);
  });
}

栈实现

使用栈可以避免递归带来的堆栈溢出问题，适合处理大规模数据。

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

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

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

      // 逆序压栈，保证顺序正确
      node.children.slice().reverse().forEach(child => {
        stack.push(child);
      });
    }
  }
}

处理图结构

对于图结构，需要额外处理循环引用问题。

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

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

    if (!visited.has(node)) {
      visited.add(node);
      console.log(node.value);

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

应用示例

假设有一个树结构：

JS实现dfs

const tree = {
  value: 1,
  children: [
    {
      value: 2,
      children: [
        { value: 4, children: [] },
        { value: 5, children: [] }
      ]
    },
    {
      value: 3,
      children: [
        { value: 6, children: [] },
        { value: 7, children: [] }
      ]
    }
  ]
};

dfs(tree); // 输出：1, 2, 4, 5, 3, 6, 7