一、核心知识点清单
1. DFS基础概念
-
定义:深度优先搜索(Depth-First Search),一种“一条路走到底”的递归搜索算法。从初始点v出发,访问v,后选择与v相邻且未被访问的点w,以w为初始点,继续访问,递归进行。
-
类比:像走迷宫时,优先选择一条路走到死胡同,再回退到上一个岔路口(回溯),直到碰到一个未走过的岔路口、继续探索。
-
核心思想:递归 + 回溯。
2. DFS递归模板(Python版)
def dfs(当前状态):if 达到终止条件: # 例如找到了解、越界、访问过记录结果或处理逻辑returnfor 选择 in 所有可能的分支: # 遍历所有子节点或方向if 不满足条件: # 剪枝(跳过无效分支)continue标记当前状态(如visited[i] = True)dfs(下一状态) # 递归进入下一层撤销标记(回溯,如visited[i] = False)
3. 术语
-
递归:函数调用自身,注意终止条件。
-
回溯:撤销上一步操作,恢复状态(关键易错点!)。
-
剪枝:提前跳过无效分支,提升效率。
4.举例说明
以这个图为例,从0开始,到1之后将1设为初始点,寻找未被遍历过且与之相邻的点3;这时将3设为初始点,继续寻找,此时的情况是,2和4均相邻且未被遍历,假设我们选择4进行下一步的初始点,访问之后已无相邻且未被遍历的点,即无满足条件的目标。此时回溯到上一初始点3,选择合适的目标2进行访问,访问完之后同样“ 到头”,继续回溯,一直都没有满足条件的目标,直到回溯到初始点0,此次搜索结束。
由此我们还可得出,dfs的搜索结果不唯一,此题中,01342和01324皆为答案。
5. 树的DFS遍历(最直观例子)
-
前序遍历:根 → 左 → 右
-
代码示例:
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef dfs(root):if not root:returnprint(root.val) # 处理当前节点dfs(root.left) # 递归左子树dfs(root.right) # 递归右子树
二、学习安排
第1个30分钟:理解概念
-
学习dfs基础知识点(例如网络视频和上述知识讲解),重点关注:
-
DFS的“深度优先”如何体现?
-
递归调用栈的执行顺序。
-
-
用纸笔画出二叉树的DFS遍历过程(如下图):
1/ \2 3/ \ 4 5
预期输出:1 → 2 → 4 → 5 → 3
第2个30分钟:手写模板
-
抄写并背诵DFS模板。
-
修改模板实现二叉树的中序遍历(左→根→右)。
def inorder(root):if not root:returninorder(root.left)print(root.val)inorder(root.right)
第3个30分钟:基础题目实战
-
题目1:二叉树的所有路径(LeetCode 257)
-
要求:输出从根节点到所有叶子节点的路径。
-
关键点:用字符串记录路径,回溯时删除末尾节点。
-
代码框架:
def binaryTreePaths(root):def dfs(node, path):if not node.left and not node.right:res.append(path + str(node.val))returnif node.left:dfs(node.left, path + str(node.val) + "->")if node.right:dfs(node.right, path + str(node.val) + "->")res = []if root: dfs(root, "")return res
-
第4个30分钟:N皇后问题
洛谷题目https://www.luogu.com.cn/problem/P1219
蓝桥n皇后题目
-
题目理解:在N×N的棋盘上放置N个皇后,使得它们互不攻击(即任意两个皇后不能在同一行、同一列或同一对角线上)。
-
简化版思路:
-
用一维数组
queens
记录每行皇后的列号。 -
DFS逐行放置皇后,检查冲突时剪枝。
-
-
代码提示:
def solveNQueens(n):def dfs(row):nonlocal resif row == n: # 所有行已放满res = [['.' * i + 'Q' + '.' * (n - i - 1) for i in queens]]returnfor col in range(n):if all(col != queens[i] and row - i != abs(col - queens[i]) for i in range(row)):queens[row] = col # 放置皇后dfs(row + 1) # 进入下一行queens = [0] * n # queens[i]表示第i行皇后的列号res = []dfs(0)return res# 测试输出一种解 print(solveNQueens(4)) # 输出示例:[['.Q..', '...Q', 'Q...', '..Q.']]
关键点解释
-
剪枝条件:
-
col != queens[i]
:检查列冲突 -
row - i != abs(col - queens[i])
:检查对角线冲突
-
-
回溯:通过
queens[row] = col
和递归后的隐式回溯(无需显式撤销,因为每次循环覆盖赋值)。
上面那个代码是输出一种解,即输出n皇后陈列放射最后的样态,如果要输出有几种摆法,还有下面一种算法。下面的代码对应的是蓝桥杯中n皇后的题目。
def NQueens(n):# 定义深度优先搜索函数,row 表示当前处理的行def dfs(row):# 当 row 等于 n 时,说明已经成功放置了 n 个皇后,方案数加 1if row == n:nonlocal countcount += 1return# 遍历当前行的每一列for col in range(n):# 检查当前列、主对角线和副对角线是否被占用if not (cols[col] or diag1[row + col] or diag2[row - col + n - 1]):# 若未被占用,标记当前列、主对角线和副对角线已被占用cols[col] = diag1[row + col] = diag2[row - col + n - 1] = True# 递归处理下一行dfs(row + 1)# 回溯操作,将当前列、主对角线和副对角线标记为未被占用cols[col] = diag1[row + col] = diag2[row - col + n - 1] = False# 初始化列标记数组,用于记录每一列是否被占用cols = [False] * n# 初始化主对角线标记数组,用于记录主对角线是否被占用diag1 = [False] * (2 * n - 1)# 初始化副对角线标记数组,用于记录副对角线是否被占用diag2 = [False] * (2 * n - 1)# 初始化方案数为 0count = 0# 从第 0 行开始进行深度优先搜索dfs(0)# 返回总的方案数return count# 读取用户输入的 n
N = int(input())
# 调用 NQueens 函数计算方案数并打印结果
print(NQueens(N))
来详细分析一下这个代码,定义一个总函数,总函数中包含dfs函数和初始化标记。
1、主函数NQueens是一个接受一个整数参数 n
的函数,n
代表棋盘的大小(即 n×n
的棋盘),函数的目的是返回在这个棋盘上放置 n
个皇后的所有可行方案的数量。
2、初始化标记
cols = [False] * ndiag1 = [False] * (2 * n - 1)diag2 = [False] * (2 * n - 1)count = 0
cols
是一个长度为n
的布尔型列表,用于标记每一列是否已经被皇后占据。初始时,所有列都未被占据,所以列表中的元素都为False
。diag1
是一个长度为2 * n - 1
的布尔型列表,用于标记从左上到右下的主对角线是否被皇后占据。因为在n×n
的棋盘上,主对角线的数量为2 * n - 1
条,所以列表长度为2 * n - 1
。初始时,所有主对角线都未被占据,元素都为False
。diag2
是一个长度为2 * n - 1
的布尔型列表,用于标记从右上到左下的副对角线是否被皇后占据。同样,副对角线的数量也是2 * n - 1
条,初始时所有副对角线都未被占据,元素都为False
。count
是一个整数变量,用于记录所有可行的放置方案的数量,初始值为 0。
这里解答一个疑问,对角线列表的元素为什么为2*n-1。这里的对角线其实指的就是每个以45度角平分正方形的每条线。不难得出,这么去切的时候,2*2的矩阵有三条线(分别是分割对角两个小正方形和分隔大正方形的最大对角线),以此类推便很容易理解。
3、深度优先搜索函数 dfs
def dfs(row):if row == n:nonlocal countcount += 1return
参数 row
为当前正在处理的行号。当 row
等于 n
时,意味着已经成功地在每一行都放置了一个皇后,找到了一种可行的放置方案。此时,使用 nonlocal
关键字引用并修改外层函数的 count
变量,将其加 1,表示找到了一种新的方案,然后返回。
4、寻找n皇后的放置位置
for col in range(n):if not (cols[col] or diag1[row + col] or diag2[row - col + n - 1]):cols[col] = diag1[row + col] = diag2[row - col + n - 1] = Truedfs(row + 1)cols[col] = diag1[row + col] = diag2[row - col + n - 1] = False
-
对于当前行
row
,遍历每一列col
。 -
cols[col]
用于检查第col
列是否已经被占据;diag1[row + col]
用于检查当前位置所在的主对角线是否已经被占据;diag2[row - col + n - 1]
用于检查当前位置所在的副对角线是否已经被占据。如果这三个条件都不满足,说明当前位置可以放置皇后。(这里如何表达对角线上的位置需要格外注意) -
如果当前位置可以放置皇后,将
cols[col]
、diag1[row + col]
和diag2[row - col + n - 1]
都标记为True
,表示该列和对应的对角线已经被占据。 -
递归调用
dfs(row + 1)
,继续处理下一行。 -
回溯操作:当递归返回时,将
cols[col]
、diag1[row + col]
和diag2[row - col + n - 1]
都标记为False
,表示撤销当前位置的皇后放置,以便尝试其他可能的放置方案。(不回溯就没有办法继续寻找其他方案)
5、调用dfs
dfs(0)return count
-
从第 0 行开始调用
dfs
函数进行深度优先搜索。 -
最后返回
count
,即所有可行的放置方案的数量。
四、常见错误提醒
-
忘记回溯:例如八皇后问题中修改
queens
后没恢复状态。 -
递归终止条件错误:导致无限递归(如二叉树遍历忘记判断
if not root
)。 -
剪枝不彻底:在排列问题中未去重,导致重复解。
五、自查清单
-
能独立写出DFS模板?
-
能解释八皇后问题的剪枝逻辑?--即什么情况下跳过分支(三个冲突)
-
能手动模拟二叉树DFS的递归栈?