当前位置：首页 > JavaScript

dfs js实现

2026-02-01 12:45:06JavaScript

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

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

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

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

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

  // 对于树结构
  if (node.children) {
    for (const child of node.children) {
      dfs(child, visited);
    }
  }

  // 对于图结构
  if (node.neighbors) {
    for (const neighbor of node.neighbors) {
      dfs(neighbor, visited);
    }
  }
}

迭代实现（使用栈）

function dfsIterative(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); // 处理当前节点

      // 注意顺序：为了保证与递归相同的遍历顺序，可能需要反转子节点
      const children = node.children ? [...node.children].reverse() : [];
      for (const child of children) {
        stack.push(child);
      }
    }
  }
}

图的DFS实现（处理循环）

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

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

    for (const neighbor of node.neighbors) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        stack.push(neighbor);
      }
    }
  }
}

使用示例

// 树节点定义
class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }
}

// 创建示例树
const root = new TreeNode(1);
const child1 = new TreeNode(2);
const child2 = new TreeNode(3);
root.children.push(child1, child2);

// 执行DFS
dfs(root);