一、什么是深度优先遍历（DFS）？
在图、树等数据结构中，**深度优先遍历（DFS）**是一种重要的遍历方式，其核心思想是“一条路走到底”，在每个分支尽可能深入，直到无法继续再回溯。
在树结构中，DFS 一般有三种形式：
- • 前序遍历（Pre-order）：根 → 左 → 右
- • 中序遍历（In-order）：左 → 根 → 右
- • 后序遍历（Post-order）：左 → 右 → 根
在图结构中，DFS 可用于：
- • 寻找路径
- • 连通分量计数
- • 拓扑排序
- • 拓展岛屿问题、迷宫路径等经典题
二、DFS vs BFS 区别一览
| 特性 | DFS（深度优先） | BFS（广度优先） |
| 结构 | 使用栈或递归 | 使用队列 |
| 遍历方式 | 一条路走到底 | 分层遍历，按距离推进 |
| 空间复杂度 | O(h)，h为深度 | O(w)，w为最大宽度 |
| 应用场景 | 拓扑排序、岛屿数量等 | 最短路径、层序遍历 |
三、DFS在树结构中的应用
示例：二叉树的前序遍历
type TreeNode struct { Val int Left *TreeNode Right *TreeNode }
方法一：递归实现
func preorderTraversal(root *TreeNode) []int { var result []int var dfs func(node *TreeNode) dfs = func(node *TreeNode) { if node == nil { return } result = append(result, node.Val) // 根 dfs(node.Left) // 左 dfs(node.Right) // 右 } dfs(root) return result }
方法二：非递归实现（使用栈）
func preorderIterative(root *TreeNode) []int { if root == nil { return nil } stack := []*TreeNode{root} var result []int for len(stack) > 0 { node := stack[len(stack)-1] stack = stack[:len(stack)-1] result = append(result, node.Val) // 注意：先右后左入栈 if node.Right != nil { stack = append(stack, node.Right) } if node.Left != nil { stack = append(stack, node.Left) } } return result }
四、DFS在图结构中的应用
图定义：
type Graph struct { adj map[int][]int } func NewGraph() *Graph { return &Graph{adj: make(map[int][]int)} } func (g *Graph) AddEdge(u, v int) { g.adj[u] = append(g.adj[u], v) g.adj[v] = append(g.adj[v], u) // 无向图 }
DFS遍历图（递归版）
func DFS(g *Graph, start int, visited map[int]bool) { if visited[start] { return } fmt.Println("访问节点:", start) visited[start] = true for _, neighbor := range g.adj[start] { if !visited[neighbor] { DFS(g, neighbor, visited) } } }
示例调用：
func main() { g := NewGraph() g.AddEdge(0, 1) g.AddEdge(0, 2) g.AddEdge(1, 3) g.AddEdge(1, 4) g.AddEdge(2, 5) visited := make(map[int]bool) DFS(g, 0, visited) }
输出顺序可能为：0 -> 1 -> 3 -> 4 -> 2 -> 5（视边顺序而定）
五、常见应用场景
| 应用场景 | 描述 |
| 二叉树遍历 | 前序、中序、后序遍历 |
| 图搜索 | 查找路径、连通分量、是否有环等 |
| 岛屿数量 | 类似图搜索，常用于二维数组（栅格图）处理 |
| 排列组合 | 回溯算法基础实现，搜索树就是 DFS |
| 迷宫问题 | 从起点探索到终点路径 |
六、经典面试题与变种
- 1. 岛屿数量问题（LeetCode 200）
用 DFS 解决二维矩阵中有多少块“1”组成的岛屿； - 2. 路径总和（LeetCode 112）
用 DFS 判断是否存在一条路径，其路径和等于给定值； - 3. 括号生成（LeetCode 22）
回溯（基于 DFS）生成所有合法括号组合； - 4. 图是否有环、是否为树
用 DFS 标记访问状态；
七、深度优先 vs 回溯算法
DFS 是回溯算法的基础。回溯是在 DFS 的基础上加上“状态恢复”的机制，在遍历路径中做出选择 → 递归探索 → 撤销选择，常用于组合、排列、子集等问题。
八、复杂度分析
对于 DFS：
- • 树结构：
- • 时间复杂度：O(n)
- • 空间复杂度：O(h)（递归栈，h 为高度）
- • 图结构：
- • 时间复杂度：O(V + E)（节点+边）
- • 空间复杂度：O(V)（访问记录）
九、调试建议与注意事项
- • DFS中需要防止死循环，特别是图结构中需要维护 visited；
- • 栈深过大时可能栈溢出，考虑改为迭代；
- • 图中有环需要特别注意：判断前访问标记；
- • 二叉树中 DFS 可用于路径、结构、镜像判断等。
十、总结
| 点位 | 内容说明 |
| 算法本质 | 基于栈的深度遍历策略 |
| 常见应用 | 树遍历、图搜索、回溯组合、路径搜索等 |
| 实现方式 | 递归或显式使用栈 |
| 注意点 | 图需维护访问标记，避免死循环 |
| 与BFS比较 | 更适合探索所有路径、搜索深层解空间 |
