当前位置：首页 > JavaScript

dfs js实现

2026-04-06 05:31:29JavaScript

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

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

dfs js实现

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

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

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

  // 遍历邻居节点（图）或子节点（树）
  for (const neighbor of node.neighbors) {
    dfs(neighbor, 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); // 处理当前节点

      // 将邻居节点逆序压入栈中（保证顺序）
      for (let i = node.neighbors.length - 1; i >= 0; i--) {
        stack.push(node.neighbors[i]);
      }
    }
  }
}

针对二叉树的DFS实现

// 前序遍历
function preorder(root) {
  if (!root) return;
  console.log(root.val);
  preorder(root.left);
  preorder(root.right);
}

// 中序遍历
function inorder(root) {
  if (!root) return;
  inorder(root.left);
  console.log(root.val);
  inorder(root.right);
}

// 后序遍历
function postorder(root) {
  if (!root) return;
  postorder(root.left);
  postorder(root.right);
  console.log(root.val);
}

图的DFS实现（处理环）

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

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

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

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