DFS深度优先搜索：核心原理+模板+力扣例题

DFS 深度优先搜索+力扣例题+模版

DFS 核心思想：一条路走到黑，碰壁就回溯，再走其他分支

一、DFS 基础概念

1. 原理

从起点出发，优先往深处走，直到走不通再回退到上一个岔路口，换方向继续搜索。

2. 关键要点

• 访问标记：图必须用，防止重复遍历死循环
• 回溯：状态用完要恢复（组合、排列等问题必备）
• 本质：利用递归 / 栈实现

3. 常见应用场景

• 岛屿数量、连通分量、省份数量
• 二叉树遍历、路径搜索
• 组合、排列、子集等回溯问题
• 迷宫搜索、拓扑排序

4. DFS vs BFS 速记

二、经典例题（Java 实现）

例题 1：LeetCode 547 省份数量（图连通性）

题目：二维数组表示城市连接关系，求有多少个连通省份。

classSolution{publicintfindCircleNum(int[][]isConnected){intn=isConnected.length;boolean[]visited=newboolean[n];intcount=0;for(inti=0;i<n;i++){if(!visited[i]){dfs(isConnected,visited,i);count++;}}returncount;}privatevoiddfs(int[][]isConnected,boolean[]visited,inti){visited[i]=true;for(intj=0;j<isConnected.length;j++){if(isConnected[i][j]==1&&!visited[j]){dfs(isConnected,visited,j);}}}}

例题 2：LeetCode 112 路径总和（二叉树 DFS）

题目：判断是否存在 根→叶子 路径，节点和等于目标值。

classSolution{publicbooleanhasPathSum(TreeNoderoot,inttargetSum){if(root==null)returnfalse;// 到达叶子节点if(root.left==null&&root.right==null){returntargetSum==root.val;}returnhasPathSum(root.left,targetSum-root.val)||hasPathSum(root.right,targetSum-root.val);}}// 树节点定义classTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(){}TreeNode(intval){this.val=val;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.val=val;this.left=left;this.right=right;}}

三、DFS 通用模板（Java 递归版）

// 通用 DFS 模板voiddfs(当前节点,状态/标记,其他参数){// 1. 终止条件if(满足边界/已访问/找到目标){记录结果;return;}// 2. 标记当前节点visited[当前]=true;// 3. 遍历所有方向/子节点for(下一个节点:可选方向){if(合法&&未访问){dfs(下一个节点,状态,参数);}}// 4. 回溯（需要时才写）visited[当前]=false;}

四、常见坑点

1. 图遍历必须加 visited，否则死循环
2. 回溯题一定要恢复状态
3. 深度过大会栈溢出，可改用迭代栈实现

五、总结

DFS 就是“递归走到底 + 回退换分支”，记住模板 + 两道例题，绝大多数搜索题都能套用。