DFS 深度优先搜索力扣例题模版DFS 核心思想一条路走到黑碰壁就回溯再走其他分支文章目录DFS 深度优先搜索力扣例题模版一、DFS 基础概念1. 原理2. 关键要点3. 常见应用场景4. DFS vs BFS 速记二、经典例题Java 实现例题 1LeetCode 547 省份数量图连通性例题 2LeetCode 112 路径总和二叉树 DFS三、DFS 通用模板Java 递归版四、常见坑点五、总结一、DFS 基础概念1. 原理从起点出发优先往深处走直到走不通再回退到上一个岔路口换方向继续搜索。2. 关键要点访问标记图必须用防止重复遍历死循环回溯状态用完要恢复组合、排列等问题必备本质利用递归 / 栈实现3. 常见应用场景岛屿数量、连通分量、省份数量二叉树遍历、路径搜索组合、排列、子集等回溯问题迷宫搜索、拓扑排序4. DFS vs BFS 速记特性DFSBFS数据结构栈队列遍历方式纵向深入逐层扩散擅长问题连通性、回溯最短路径二、经典例题Java 实现例题 1LeetCode 547 省份数量图连通性题目二维数组表示城市连接关系求有多少个连通省份。classSolution{publicintfindCircleNum(int[][]isConnected){intnisConnected.length;boolean[]visitednewboolean[n];intcount0;for(inti0;in;i){if(!visited[i]){dfs(isConnected,visited,i);count;}}returncount;}privatevoiddfs(int[][]isConnected,boolean[]visited,inti){visited[i]true;for(intj0;jisConnected.length;j){if(isConnected[i][j]1!visited[j]){dfs(isConnected,visited,j);}}}}例题 2LeetCode 112 路径总和二叉树 DFS题目判断是否存在 根→叶子 路径节点和等于目标值。classSolution{publicbooleanhasPathSum(TreeNoderoot,inttargetSum){if(rootnull)returnfalse;// 到达叶子节点if(root.leftnullroot.rightnull){returntargetSumroot.val;}returnhasPathSum(root.left,targetSum-root.val)||hasPathSum(root.right,targetSum-root.val);}}// 树节点定义classTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(){}TreeNode(intval){this.valval;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.valval;this.leftleft;this.rightright;}}三、DFS 通用模板Java 递归版// 通用 DFS 模板voiddfs(当前节点,状态/标记,其他参数){// 1. 终止条件if(满足边界/已访问/找到目标){记录结果;return;}// 2. 标记当前节点visited[当前]true;// 3. 遍历所有方向/子节点for(下一个节点:可选方向){if(合法未访问){dfs(下一个节点,状态,参数);}}// 4. 回溯需要时才写visited[当前]false;}四、常见坑点图遍历必须加 visited否则死循环回溯题一定要恢复状态深度过大会栈溢出可改用迭代栈实现五、总结DFS 就是“递归走到底 回退换分支”记住模板 两道例题绝大多数搜索题都能套用。