深度优先搜索（DFS）

DFS 的核心是“先深后回头”。它不保证最短，但特别适合做连通性、路径存在性、回溯和子问题递归。

定义

**深度优先搜索（Depth-First Search, DFS）**是一种图遍历算法，沿着图的深度尽可能远地搜索，直到到达死胡同后再回溯。

图的DFS遍历:
    1
   / \
  2   3
 / \   \
4   5   6

DFS顺序: 1 → 2 → 4 → 5 → 3 → 6

🎞️ 深入与回溯动画

（附件 dfs-backtrack.svg 未随站点发布）

看动画时重点盯住“当前路径”

DFS 不是在全图平均推进，而是先把一条路径走到底；只有当前分支结束，才会回到上一个岔路口。

核心思路

• 递归探索：从起点开始，尽可能深地访问每个分支
• 回溯机制：到达死胡同时返回上一层继续探索
• 访问标记：使用visited集合避免重复访问
• 栈结构：递归调用栈或显式栈实现

为什么 DFS 特别适合递归题

因为很多题本来就是“当前点的答案依赖子节点答案”的结构：

• 树遍历
• 连通块搜索
• 回溯枚举
• 拓扑 / Tarjan 这类基于递归栈的图算法

只要你能清楚定义“进入当前节点要做什么、离开当前节点要做什么”，DFS 通常就很自然。

复杂度分析

指标	复杂度	说明
时间复杂度	O(V+E)	V是顶点数，E是边数
空间复杂度	O(V)	递归栈或显式栈
最坏情况	O(V+E)	遍历所有节点和边

Go 代码

Go 实现

package main
 
// DFS递归实现
func DFSRecursive(graph [][]int, start int) []int {
    visited := make(map[int]bool)
    result := []int{}
 
    var dfs func(int)
    dfs = func(node int) {
        if visited[node] {
            return
        }
 
        visited[node] = true
        result = append(result, node)
 
        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                dfs(neighbor)
            }
        }
    }
 
    dfs(start)
    return result
}
 
// DFS迭代实现
func DFSIterative(graph [][]int, start int) []int {
    visited := make(map[int]bool)
    result := []int{}
    stack := []int{start}
 
    for len(stack) > 0 {
        // 弹出栈顶元素
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
 
        if visited[node] {
            continue
        }
 
        visited[node] = true
        result = append(result, node)
 
        // 逆序压栈
        for i := len(graph[node]) - 1; i >= 0; i-- {
            neighbor := graph[node][i]
            if !visited[neighbor] {
                stack = append(stack, neighbor)
            }
        }
    }
 
    return result
}
 
// 遍历所有连通分量
func DFSAllComponents(graph [][]int) []int {
    visited := make(map[int]bool)
    result := []int{}
 
    var dfs func(int)
    dfs = func(node int) {
        if visited[node] {
            return
        }
 
        visited[node] = true
        result = append(result, node)
 
        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                dfs(neighbor)
            }
        }
    }
 
    for node := range graph {
        if !visited[node] {
            dfs(node)
        }
    }
 
    return result
}

思路展开

DFS的执行过程

以下图为例：

    1
   / \
  2   3
 /     \
4       5

递归DFS执行过程：

1. 访问节点1，标记为已访问
2. 递归访问节点1的第一个邻接节点2
3. 递归访问节点2的邻接节点4
4. 节点4无未访问邻接节点，回溯到节点2
5. 节点2无其他未访问邻接节点，回溯到节点1
6. 递归访问节点1的第二个邻接节点3
7. 递归访问节点3的邻接节点5
8. 完成遍历

访问顺序：1 → 2 → 4 → 3 → 5

DFS 的应用场景

1. 路径查找：判断两点间是否存在路径
2. 连通性检测：判断图是否连通
3. 环检测：检测图中是否存在环
4. 拓扑排序：有向无环图的拓扑排序
5. 强连通分量：Tarjan算法、Kosaraju算法

易错点

DFS 题最容易错的不是搜索本身，而是状态管理。

• 图有环时必须做 visited。
• 回溯题里 visited 是否需要撤销，要看状态是不是“路径级”的。
• 递归版写起来短，但图很深时要注意栈深风险。
• 迭代版如果想和递归版顺序一致，通常要逆序压栈。

经典题目

优缺点

优点

• ✅ 实现简单，代码简洁
• ✅ 适合路径查找和连通性问题
• ✅ 可以轻松检测环
• ✅ 空间效率高（只需O(V)）

缺点

• ❌ 不保证找到最短路径
• ❌ 可能陷入深度很大的分支
• ❌ 递归实现可能栈溢出

相关主题

• BFS - 层次遍历的替代方案
• DFS基础模板 - 更通用的模板页
• DFS拓扑排序 - DFS的应用
• 强连通分量 - Tarjan算法使用DFS
• 岛屿数量 - DFS经典应用
• 图算法 - 返回图算法总览

---

返回：图算法 | 算法学习导航