给学生讲完深度优先搜索（DFS）的二叉树遍历，总有人追着问：这玩意儿在真实问题里到底长什么样？翻来覆去想了几天，我从一堆课后题里拎出了农夫过河。别看它题干只有一句话——一个农夫、一匹狼、一只羊、一筐白菜，一只一次只能坐农夫加一样东西的小船——它的状态空间小到能手工枚举，又完整覆盖了DFS的递归、回溯、去重、剪枝所有环节。这篇文章适合正在学DFS、或者想搞明白“搜索算法解决的到底是什么问题”的读者。读完你会发现，原来写递归不是靠感觉，而是靠一张先在纸上画清楚的状态图。
1. 为什么我把农夫过河当作理解DFS的入场题
1.1 一读就懂的问题规则
农夫要划船把狼、羊、白菜全部从河左岸运到右岸。船只有两个位置：农夫自己，外加最多一样东西。难点在于三条约束：农夫不在场时，狼会吃羊；农夫不在场时，羊会吃白菜；而狼和白菜单独待在一起反而没问题，因为狼不吃白菜。换句话说，核心危险角色是羊，狼和白菜不能分别与它独处。
这个问题在很多教材里被归入“经典搜索题”，和八皇后、迷宫、传教士过河并列。我之所以先拿它开刀，是因为它比迷宫更贴近日常直觉：迷宫里你至少看得见路，过河问题你根本不知道下一步“合法的选择”有哪些，必须自己把所有可能性枚举出来。而枚举可能性这件事，正是搜索算法要做的事。
1.2 直觉盲试为什么必然折返
不懂算法的人也能靠人工推理硬解这个题，方法就是“试”：先带羊过去，空船回来，再带狼过去，再把羊带回来……但如果你没有章法地瞎试，很容易陷入重复。比如你把狼带过去之后，发现左岸的羊和白菜没人看管，只好把狼又带回来；再试带白菜，发现左岸的狼和羊又打起来了；绕来绕去，可能十分钟过去了，船还在原地。
这个“重复”就是搜索算法存在的理由。人脑盲试的时候很难记住全部试过的状态，计算机用一个小小的set就能做到。DFS在这个问题里做的事，本质上是把“瞎试”变成“有记忆的、系统的瞎试”：一条路走不通就退回上一个岔路口，走另一条；走过的状态绝对不再走第二次。
1.3 DFS在这道题里的角色
如果用一句话概括DFS在这个问题里的定位：它负责在合法的状态之间移动，利用回溯机制处理走不通的分支，利用visited集合处理回头路，最终找到一条从初始状态到目标状态的合法路径。它不保证这条路径最短，只保证“找得到”。搞清楚这个定位很重要，因为后面你会发现，农夫过河由于状态空间极小，DFS表现很好，但一旦问题规模变大，这种“找到就行”的作风就会带来麻烦。
2. 16个状态还是10个状态：动手写递归前先把图建出来
2.1 用0和1给河岸编码
我见过很多人一上来就写递归，写了半天不知道终止条件怎么定。问题的根源在于没有建模。农夫过河一共四个对象：农夫、狼、羊、白菜。每个对象只有两种位置：左岸或右岸。所以完整的状态空间是2的4次方，一共16个状态。
实际编码时，我用一个四元组(f, w, s, c)表示当前状态，四个位置从左到右分别代表农夫、狼、羊、白菜。其中1表示在左岸，0表示在右岸。初始状态是(1, 1, 1, 1)，表示四个对象全在左岸；目标状态是(0, 0, 0, 0)，表示全在右岸。这样设计的好处是：右岸的信息不需要额外记录，右岸就是“值为0的那些东西”，一个元组同时表达了两个岸的情况。
为什么要专门说这个？因为很多初学者喜欢用两个列表分别记录左岸和右岸，转移的时候同步维护两个列表，极其容易出错。用0/1编码后，一次过河动作只需要把对应位置从0变1或从1变0，简单直接。
2.2 6个非法状态，一次筛干净
16个状态不是都能用的。根据“狼和羊不能独处、羊和白菜不能独处”这条规则，我手工枚举了一遍，非法状态一共有6个，见下表。
| 非法状态 (f, w, s, c) | 实际场景 | 违规原因 |
|---|---|---|
| (1, 1, 0, 0) | 左岸：农夫、狼；右岸：羊、白菜 | 右岸羊和白菜独处 |
| (1, 0, 0, 1) | 左岸：农夫、白菜；右岸：狼、羊 | 右岸狼和羊独处 |
| (1, 0, 0, 0) | 左岸：农夫；右岸：狼、羊、白菜 | 右岸狼吃羊、羊吃白菜 |
| (0, 1, 1, 1) | 左岸：狼、羊、白菜；右岸：农夫 | 左岸狼吃羊、羊吃白菜 |
| (0, 1, 1, 0) | 左岸：狼、羊；右岸：农夫、白菜 | 左岸狼和羊独处 |
| (0, 0, 1, 1) | 左岸：羊、白菜；右岸：农夫、狼 | 左岸羊和白菜独处 |
16个状态去掉6个非法状态，剩下10个合法状态。初始状态和目标状态都在合法集合里。这个结论是可以直接作为代码注释写进去的：一个状态合法，当且仅当“没有农夫的那一岸，不同时出现狼和羊，也不同时出现羊和白菜”。
2.3 状态转移：可逆的“农夫动作”
状态之间的连接关系来自农夫的动作。农夫每次过河，可以做两件事之一：要么独自过河，要么带一个与自己同岸的东西过河。不管哪种情况，农夫的位置一定取反；如果带了东西，那个东西的位置也取反。
这个转移有一个非常重要的性质：它是可逆的。如果状态A能通过“农夫带羊从左到右”到达状态B，那么B一定能通过“农夫带羊从右到左”回到A。也就是说，整个合法状态图是无向的。这个性质对DFS意义重大：回溯之所以成立，就是因为我们总能沿着来路退回去。
如果把10个合法状态按转移关系连起来，会得到一张非常小的无向图。DFS在这张图上走，本质上和一个带记忆的人走迷宫没有区别。
3. 完整代码：递归、回溯、visited是如何一起工作的
3.1 先写合法性判断
代码第一块是合法性判断函数。核心逻辑就是顺着2.2的规则翻译：
def is_valid(state): f, w, s, c = state # 农夫不在左岸时，左岸不能留下“狼+羊”或“羊+白菜” if f == 0 and ((w == 1 and s == 1) or (s == 1 and c == 1)): return False # 农夫不在右岸时，右岸不能留下“狼+羊”或“羊+白菜” if f == 1 and ((w == 0 and s == 0) or (s == 0 and c == 0)): return False return True这段代码对应着“狼吃羊、羊吃白菜”的全部危险组合。注意我用的是右岸状态取补的方式：w == 0表示狼不在左岸，即在右岸。理解了这个补集逻辑，后面的状态转移代码才读得懂。
3.2 再写邻居生成
邻居生成函数负责从当前状态算出农夫一次过河后，可能到达哪些合法状态。逻辑分三步：农夫位置取反；判断农夫在左岸还是右岸，从而决定能带哪些同岸物品；逐个尝试并过滤非法结果。
def get_neighbors(state): f, w, s, c = state nf = 1 - f # 农夫必然过河，位置取反 result = [] # 情况一：农夫独自过河 ns = (nf, w, s, c) if is_valid(ns): result.append(ns) # 情况二：农夫带一个物品过河，物品必须与农夫同岸 items = [] if f == 1: # 农夫在左岸 if w == 1: items.append('w') if s == 1: items.append('s') if c == 1: items.append('c') else: # 农夫在右岸 if w == 0: items.append('w') if s == 0: items.append('s') if c == 0: items.append('c') for item in items: if item == 'w': ns = (nf, 1 - w, s, c) elif item == 's': ns = (nf, w, 1 - s, c) else: ns = (nf, w, s, 1 - c) if is_valid(ns): result.append(ns) return result这段代码有一个隐含细节：我先把“独自过河”放进候选列表，再枚举带物品的情况。这个顺序会影响DFS最终搜索路径。后面第4章你会看到，仅仅调换这个顺序，输出路径就可能完全不同。
3.3 最后写DFS主流程
主流程是标准的三件套：visited集合、path列表、递归函数。我把完整代码贴出来：
INIT_STATE = (1, 1, 1, 1) # 农夫、狼、羊、白菜都在左岸 GOAL_STATE = (0, 0, 0, 0) # 全部移到右岸 visited = set() path = [] def dfs(state): if state == GOAL_STATE: return True visited.add(state) for ns in get_neighbors(state): if ns in visited: continue path.append(ns) if dfs(ns): return True path.pop() # 回溯：撤销当前选择 return False path.append(INIT_STATE) dfs(INIT_STATE) print('搜索过程中访问过的状态数:', len(visited)) print('完整路径（含起点）:') for i, s in enumerate(path): print(f'第{i}步: {s}')这里有几个关键点必须解释清楚。第一，visited必须是集合而不是列表，因为状态只有10个合法值，用集合的查找是O(1)，量级大了这个差距会非常明显。第二，path记录的是从起点到当前状态的完整路径，它和visited是两个东西：visited管“别走回头路”，path管“最后输出答案”。第三，回溯发生在path.pop()这行，它的含义是：当前状态的所有邻居都试完且都失败，撤销刚才的选择，回到上一层递归继续尝试别的分支。
不少初学者会把visited和path混为一谈，用if ns not in path代替if ns in visited。在这个小问题里运气好也能跑通，但一旦状态图出现环，就会陷入死循环。因为path保存的是当前这一条路径上的节点，不是“历史上所有到过的节点”。这一步的差别，是DFS面试里最常见的坑之一。
4. 跑通之后看细节：DFS探索了哪些状态，又错过了哪些
4.1 运行输出和路径翻译
我按上面代码原样运行，输出如下：
搜索过程中访问过的状态数: 8 完整路径（含起点）: 第0步: (1, 1, 1, 1) 第1步: (0, 1, 0, 1) 第2步: (1, 1, 0, 1) 第3步: (0, 0, 0, 1) 第4步: (1, 0, 1, 1) 第5步: (0, 0, 1, 0) 第6步: (1, 0, 1, 0) 第7步: (0, 0, 0, 0)把这串状态翻译成人话，就是经典的七步答案：
- 农夫带羊过河，左岸剩下狼和白菜；
- 农夫空船返回左岸；
- 农夫带狼过河，右岸变成农夫、狼、羊，左岸只剩白菜；
- 农夫带羊返回左岸，防止狼吃羊；
- 农夫带白菜过河，右岸变成农夫、狼、白菜，左岸只剩羊；
- 农夫空船返回左岸；
- 农夫带羊过河，完成。
看到没有，整个过程中羊被折腾得最惨，来回被带了三次。这不是算法偏心，而是羊同时是狼和白菜的天敌，它是唯一的“冲突枢纽”，必须反复押送。
4.2 8个visited状态背后，DFS放弃了什么
有趣的是，10个合法状态里DFS只访问了8个，有2个合法状态自始至终没有出现在路径里：(1, 1, 1, 0)表示“左岸是农夫、狼、羊，右岸是白菜”，(0, 1, 0, 0)表示“左岸只有狼，右岸是农夫、羊、白菜”。这两个状态之所以没被访问，是因为DFS一进入某条分支就直奔目标去了，压根没有机会试探另一条分支。
这就是DFS最典型的性格：宁可一条道走到目标，也不愿意先把所有邻居都看一遍。在农夫过河这个图里，10个状态太少了，所以它看起来“很聪明”，一步冤枉路都没多走。但换成状态空间更大的问题，这种一根筋的走法就可能把它带进一条很长的死路，浪费大量时间。理解这一点，才算真正理解了为什么有时候DFS会“碰巧”很快，有时候又“离奇”地慢。
4.3 换一种遍历顺序，结果可能完全不一样
我在3.2节提到过，get_neighbors里候选状态的枚举顺序会直接影响DFS的输出。如果把候选顺序改成“先带羊、再带狼、再空船、再带白菜”，初始状态下第一个合法邻居仍然是带羊，但走到(1, 1, 0, 1)这个状态时，DFS会优先尝试带白菜过河，走另一条分支。
我在本地试过调整顺序后的结果，路径完全变了：
第0步: (1, 1, 1, 1) 第1步: (0, 1, 0, 1) 第2步: (1, 1, 0, 1) 第3步: (0, 1, 0, 0) 第4步: (1, 1, 1, 0) 第5步: (0, 0, 1, 0) 第6步: (1, 0, 1, 0) 第7步: (0, 0, 0, 0)这条路径也是7步，但中间过程完全不同：先带狼过去再带白菜，羊在中间只被带了一次，比之前的解法少折腾了一趟。这个现象说明，对于同一个问题，DFS的输出很大程度取决于邻居的枚举顺序。如果枚举顺序不好，DFS可能找到一条明显绕弯的路径，甚至在某些问题里走了指数级的长路才到达目标。
4.4 调试DFS的实用方式：递归缩进打印
写DFS的时候，我最推荐一个调试技巧：在递归函数进出时打印状态，并用缩进表示递归深度。代码改动极小：
depth = 0 def debug_dfs(state): global depth if state == GOAL_STATE: print(' ' * depth + f'到达目标 {state}') return True print(' ' * depth + f'进入 {state}') visited.add(state) depth += 1 for ns in get_neighbors(state): if ns in visited: continue path.append(ns) if debug_dfs(ns): return True path.pop() depth -= 1 print(' ' * depth + f'回退 {state}') return False输出会呈现一棵清晰的递归树。你会看到“进入 (1,1,0,1)”之后，尝试某个邻居，被打回，再尝试另一个。这个打回的过程就是回溯。很多学生看完这棵缩进树，才真正明白“递归调用栈”是什么概念。这个方法我几乎在每个搜索类题目上都会用，比单步调试高效得多。
5. 约束一改，结论就变：容量升级和物品扩容下的算法选择
5.1 如果船一次能带两件物品
把问题里的船升级一下：一次能带两样东西。这个改动看似简单，状态图和转移关系立刻变复杂。从初始状态(1, 1, 1, 1)出发，农夫可以选择带“狼+羊”“羊+白菜”“狼+白菜”甚至任意两件组合，其中“狼+白菜”的组合直接让左岸只剩羊，右岸是农夫、狼、白菜，一步就把大部分问题解决了。
我用带两件的转移逻辑跑了一下，DFS仍然能找到解，但路径出现了明显的不同：如果枚举顺序是单件优先，DFS会先试单件，先绕到7步以上的路径；如果枚举顺序是双件优先，3步就能结束。这个例子非常直观地说明：约束越少，转移越密，DFS“走错分支再退回”的机会成本越高。而BFS在这种转移密集的图里，反而能更快给出最短解。
5.2 物品数量变大时DFS的处境
假设把物品从3样增加到4样、5样，状态数量会从16个变成32个、64个。表面上看数量依然不大，但合法状态和转移边数可能增长得更快。更麻烦的是，如果存在一条很长的非法分支，DFS会一头扎进去，一直扎到最深处才发现此路不通，然后慢慢回溯。这种“深钻”行为在最坏情况下会访问指数级的状态。
实际工程里我很少用深度优先来处理这种小规模组合问题，除非明确只需要“找到一个可行解”。如果既要找解、又要证明步数最少，那优先选BFS；如果状态空间大到BFS内存放不下，就考虑迭代加深。所谓迭代加深，就是反复用DFS，但每次都设置一个最大深度，第一轮限制只能走3步，第二轮限制只能走5步，依此类推。它既保留了DFS的低空间占用，又能像BFS一样保证首次找到的路径是短路径。
5.3 DFS和BFS的选择题
还是回到农夫过河本身。假设现在问你：是否存在一条不超过5步的合法方案？DFS不会回答这个问题，因为它找到的第7步解只能证明“有解”。要证明“5步内有解”，你必须把所有不超过5步的状态全部展开，这正是BFS的活。
| 对比维度 | DFS | BFS |
|---|---|---|
| 空间占用 | 只存当前路径，小 | 需要存整层节点，可能大 |
| 是否保证最短路径 | 不保证 | 保证 |
| 迷宫/连通性问题 | 很合适，找路快 | 也能做，但空间消耗大 |
| 状态数量爆炸的组合题 | 容易深陷错误分支 | 层次推进，可靠但慢 |
| 农夫过河这类小状态题 | 足够用 | 完全够用，且路径最短 |
我给读者的建议很简单：先看问题要什么。只求“有没有解”，优先DFS；求“最少几步”“最短路径”，优先BFS。农夫过河是少有的两者都能轻松搞定的题目，正好适合拿来做对比实验。
5.4 用BFS写一遍，马上看出两种算法的气质差异
BFS的代码也很短，我用队列实现，每个队列元素保存状态和到达该状态的完整路径：
from collections import deque def bfs(): start = INIT_STATE if start == GOAL_STATE: return [start] queue = deque() queue.append((start, [start])) visited = {start} while queue: state, path = queue.popleft() for ns in get_neighbors(state): if ns in visited: continue new_path = path + [ns] if ns == GOAL_STATE: return new_path visited.add(ns) queue.append((ns, new_path)) return None跑出来的结果同样是7步路径，但它能保证“不可能少于7步”。这就是BFS给你的一颗定心丸。相比之下，DFS给不出这样的保证，它只是第一个冲过终点线的选手。
6. 这个题目讲完，我最想对你说的三件事
6.1 纸上画状态图，比写递归更重要
这句话我几乎每次讲搜索都会强调。农夫过河的完整状态图只有10个合法节点，用笔在纸上画出来，连好转移边，再回头看代码，递归的每一步都对应图上的某一条边。一旦做到这个对应关系，DFS就从一个“玄乎的递归”变成了一个“在图上老老实实走路的程序”。
我自己初学DFS时也犯过这个错误：抱着代码啃，反复看递归过程，越看越糊涂。后来把迷宫状态图画出来，用笔模拟递归指针移动，半小时就通了。
6.2 最常见的一个bug：visited用错了地方
我帮人改过很多次DFS代码，发现最有代表性的错误就是那类“用path代替visited”的写法。问题代码往往长这样：
# 错误示范：用 path 去重 if ns not in path: path.append(ns) dfs(ns) path.pop()在小状态图上它可能侥幸跑通，但一旦状态图出现环，或者同一个状态可以通过不同路径再次到达，程序要么死循环，要么重复搜索大量分支。正确的做法是让visited独立记录所有被访问过的状态，path只负责记录当前路径。这个坑在二叉树上完全不会出现，因为树没有环；换成图一下子就暴露了。农夫过河正好是“从树到图”的过渡题，踩一次这个坑，后面写图的DFS基本就不会再犯了。
6.3 下一步可以玩什么变体
觉得农夫过河太简单的话，我建议试着这么改：限制总步数，要求DFS在中途剪枝；把船容量改成2并把物品变成4样；或者比较不同枚举顺序下DFS访问状态数的变化。这些改动都不大，但每一个都能让你对搜索算法多一层体感。
我个人这两年讲这个题最大的体会是：经典题的价值不在于题本身有多难，而在于它能不能让人在一张白纸上把思路完整铺开。农夫过河恰好做到了这一点——状态少、规则清晰、结果可人工验证。如果你正在学DFS，别急着刷一堆迷宫题，先把这道题跑通、画懂、改烦，再往前走。
