# 深度优先搜索

比较次数: 0

已访问节点:

# 算法原理

深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。它的基本思想是从一个顶点开始，沿着一条路径一直走到底，然后回溯到上一个节点，继续探索其他路径，直到访问完所有可达的顶点。

# 算法步骤

从起始顶点开始，标记它为已访问
递归地访问该顶点的每个未访问的相邻顶点
如果某个相邻顶点没有未访问的相邻顶点，则回溯到上一个顶点
重复步骤2和3，直到所有顶点都被访问

# 代码实现

// 递归实现（邻接表表示）
function dfs(graph, start, visited = new Set()) {
  // 标记当前顶点为已访问
  visited.add(start);
  console.log(start);  // 访问顶点
  
  // 递归访问所有未访问的相邻顶点
  for (const neighbor of graph[start]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited);
    }
  }
}

// 非递归实现（使用栈）
function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];
  
  while (stack.length > 0) {
    const vertex = stack.pop();
    
    if (!visited.has(vertex)) {
      visited.add(vertex);
      console.log(vertex);  // 访问顶点
      
      // 将未访问的相邻顶点压入栈中
      for (const neighbor of graph[vertex]) {
        if (!visited.has(neighbor)) {
          stack.push(neighbor);
        }
      }
    }
  }
}

// 在二叉树中使用DFS
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

// 前序遍历（根-左-右）
function preorderDFS(root) {
  if (root === null) return;
  
  console.log(root.val);  // 访问根节点
  preorderDFS(root.left); // 遍历左子树
  preorderDFS(root.right);// 遍历右子树
}

// 中序遍历（左-根-右）
function inorderDFS(root) {
  if (root === null) return;
  
  inorderDFS(root.left);  // 遍历左子树
  console.log(root.val);   // 访问根节点
  inorderDFS(root.right); // 遍历右子树
}

// 后序遍历（左-右-根）
function postorderDFS(root) {
  if (root === null) return;
  
  postorderDFS(root.left); // 遍历左子树
  postorderDFS(root.right);// 遍历右子树
  console.log(root.val);   // 访问根节点
}

# 复杂度分析

# 时间复杂度

O(V + E)，其中V是顶点数，E是边数
对于树形结构：O(n)，其中n是节点数

# 空间复杂度

递归实现：O(h)，h是图的深度或树的高度（递归调用栈的开销）
非递归实现：O(V)，需要visited集合和栈来存储顶点

# 算法特点

# 优点

实现简单，容易理解
空间复杂度相对较低
适合搜索深层次的结构
可以用于检测环和寻找路径

# 缺点

可能会陷入很深的分支
不一定能找到最短路径
对于广度很大的图，效率可能不如BFS

# 适用场景

遍历树形结构
查找图中的路径或环
解决迷宫问题
拓扑排序
查找连通分量

# 实际应用

文件系统遍历
游戏中的路径查找
编译器的语法分析
社交网络中的关系链分析

# 优化方案

剪枝：在某些条件下提前结束搜索
记忆化：存储已经计算过的结果
迭代加深：逐步增加搜索深度

// 带剪枝的DFS示例（查找目标值）
function dfsWithPruning(graph, start, target, visited = new Set()) {
  if (start === target) {
    return true;  // 找到目标，提前结束搜索
  }
  
  visited.add(start);
  
  for (const neighbor of graph[start]) {
    if (!visited.has(neighbor)) {
      if (dfsWithPruning(graph, neighbor, target, visited)) {
        return true;  // 在某个分支中找到目标
      }
    }
  }
  
  return false;  // 当前分支未找到目标
}

// 迭代加深DFS
function iterativeDeepeningDFS(graph, start, maxDepth) {
  for (let depth = 0; depth <= maxDepth; depth++) {
    const visited = new Set();
    if (dfsWithDepth(graph, start, depth, visited)) {
      return true;  // 在当前深度找到目标
    }
  }
  return false;  // 在限定深度内未找到目标
}

function dfsWithDepth(graph, vertex, depth, visited) {
  if (depth === 0) {
    return vertex === target;  // 到达目标深度，检查是否为目标顶点
  }
  
  visited.add(vertex);
  
  for (const neighbor of graph[vertex]) {
    if (!visited.has(neighbor)) {
      if (dfsWithDepth(graph, neighbor, depth - 1, visited)) {
        return true;
      }
    }
  }
  
  visited.delete(vertex);  // 回溯时移除访问标记
  return false;
}

← 广度优先搜索排序算法 →