企业官网建设流程全解析

深度优先搜索（Depth First Search，DFS）是我在工作里用得最多的算法之一，但每次给新人讲透一个算法的精髓，我最爱用的例子反而不是什么高深的图论题，而是这个流传了好几十年的农夫过河问题。很多人觉得它就是个脑筋急转弯，但如果你真把它抽象成状态空间的搜索问题，再用深度优先的框架去实现一遍，你会发现这个例子几乎把DFS的核心机制——状态建模、剪枝、回溯、路径还原——全部串起来了。这篇文章我就用完整的可运行代码加推演过程，把这个经典问题彻底讲透，顺便聊一聊为什么深度优先在这个场景里是比广度优先更顺手的选择。

这个问题我先后在课程设计、新手培训、甚至面试题库里见过好几个变体，但不管怎么改，核心逻辑都是同一套。适合正在学算法、准备面试，或者想搞明白DFS到底怎么落地到实际场景的人。看完你不仅能独立写出求解代码，还能理解为什么有些写法会陷入死循环、为什么路径不一定最短、以及怎么把这种建模思路迁移到别的问题上。

1. 问题本质与算法选型——为什么要用深度优先

1.1 农夫过河到底是个什么问题

原题是这样的：农夫要带狼、羊、白菜过河，河边只有一条小船，农夫划船，每次只能带一样东西过河。这里有几个约束：如果农夫不在场，狼会吃羊，羊会吃白菜。问怎么才能把所有东西都安全运到对岸。

教科书里的解法通常是手动推演几步，但作为程序员，我们应该把它看成一个状态搜索问题。所谓状态，就是“此刻农夫、狼、羊、菜分别在河的哪一边”。每个状态下，农夫可以执行若干合法动作（单独过河、带某样东西过河），到达下一个状态。我们的目标是从初始状态出发，找到一条通向成功状态的路径。

这其实就是一个图遍历问题。节点是状态，边是动作，路径就是过河方案。弄清楚这一点后，问题就变得特别规整了——用搜索算法遍历状态图，找到初始节点到目标节点的路径就行。

1.2 为什么深度优先比广度优先更合适

初学者很容易想到用广度优先搜索（BFS），因为它天然保证找到的路径是最短的。但你要真去实现一遍就会发现，BFS需要维护一个较大的队列，因为每一层的状态数量是爆炸式增长的。而农夫过河的状态空间并不大，但DFS会带给你一个额外的好处：空间占用极小，只要沿着一条路走到底。

更重要的是，很多实际场景中我们关心的不是最短路径，而是“是否存在可行路径”和“这条路径具体是什么”。DFS在这种场景下资源开销更可控，代码也更简洁。对于一个状态数有限的问题，DFS加上合理的剪枝，跑起来非常快。

我用生活化类比来说明：BFS像地毯式排查，一层一层推进，保证第一个找到的出口一定最近，但需要记住所有待排查的位置；DFS像走迷宫时一直沿右边墙走，不回头地走到死路才返回换路，不需要记太多岔路口的信息，但找到的路未必是最短的。

这道题里面，状态数量总共就16个（四种东西各有两个位置，2的4次方），无论用哪种搜索都能瞬间出结果。但为了教学和训练算法思维，DFS是更合适的选择——它能让你更清晰地理解“递归 + 回溯”这套核心机制，而这套机制在后面的拓扑排序、连通分量、回溯法解题里都会反复用到。

2. 状态空间建模——把现实问题翻译成程序语言

2.1 状态编码：用二进制位表示四个角色的位置

我第一版代码里用的是结构体数组来存状态，字段分别是farmer、wolf、sheep、cabbage，每个字段取0或1，0表示在左岸（起点），1表示在右岸（终点）。后来发现完全可以用一个四位二进制来编码，每一位代表一个角色的位置。

bit0: 农夫 bit1: 狼 bit2: 羊 bit3: 白菜

用0和1表示左岸和右岸，这样初始状态就是0000，目标状态就是1111。每次渡河动作的本质，就是对状态值的某些位进行翻转。

这种编码的妙处在于：判断状态是否重复时，直接比较整型值；计算下一个状态时，用位运算几行就搞定了；打印状态时，再把每一位拆出来翻译成文字即可。

代码里我用一个整型变量state来保存当前状态，枚举顺序固定为农夫、狼、羊、菜，读的时候用位运算从低位往高位取：

int is_on_right(int state, int role) { return (state >> role) & 1; }

这里role取0到3，分别对应农夫、狼、羊、菜。判断某个角色在不在右岸，只需要把状态右移对应位数再和1做按位与。判断在左岸，结果取反即可。

2.2 合法状态判断：狼和羊、羊和菜不能单独相处

状态合法性的判断是这个问题的第一个关键点。安全状态的条件是：如果农夫不在某一边，那这一边不能同时存在“狼和羊”或者“羊和菜”。

我把这部分独立成一个函数：

int is_valid(int state) { // 如果农夫和狼在同一侧，或者狼不在羊这一侧，才安全 // 直接分情况讨论更清晰 if (is_on_right(state, FARMER) == is_on_right(state, WOLF)) { // 农夫和狼同侧，安全区，继续判断羊和菜 } else { // 农夫不在狼这边，狼和羊不能同侧 if (is_on_right(state, WOLF) == is_on_right(state, SHEEP)) { return 0; } } if (is_on_right(state, FARMER) == is_on_right(state, SHEEP)) { // 农夫和羊同侧，安全区 } else { if (is_on_right(state, SHEEP) == is_on_right(state, CABBAGE)) { return 0; } } return 1; }

这里初学者容易犯一个错误，就是把判断条件写反。之前带一个实习生，他写的是“如果农夫不在场且狼羊同侧就是合法”，结果程序跑出来一堆“狼吃羊”的路径还在继续往下走。这里的逻辑是：非法情况要显式排除，剩下的才是合法。

我后来把判断改成更简洁的位运算版本，判断“农夫不在一侧”等价于判断“农夫位置与某个角色位置不等”，然后你只需排除“狼羊同侧”和“羊菜同侧”两种危险组合：

int is_valid(int state) { if (is_on_right(state, WOLF) == is_on_right(state, SHEEP) && is_on_right(state, FARMER) != is_on_right(state, WOLF)) { return 0; // 狼羊同侧且农夫不在，狼会吃羊 } if (is_on_right(state, SHEEP) == is_on_right(state, CABBAGE) && is_on_right(state, FARMER) != is_on_right(state, SHEEP)) { return 0; // 羊菜同侧且农夫不在，羊会吃菜 } return 1; }

简洁、直观、不容易出错。这个函数是整棵搜索树的过滤器，每走一步都必须用它把关。

2.3 动作集合：四种渡河选择的枚举

从一个状态出发，农夫能做的动作总共有四种：

• 农夫独自过河（不带任何东西）
• 农夫带狼过河
• 农夫带羊过河
• 农夫带白菜过河

但要注意，农夫带某样东西过河的前提是：这样东西此刻和农夫在同一边。你不可能在左岸的时候带着已经在右岸的狼过河。

所以每次探索时，我的逻辑是遍历四样东西（包含一个“空”选项），检查这个东西是否和农夫在同一侧，如果是，则生成新的状态。生成新状态的方法是让对应位翻转：农夫所在位翻转，携带物品的所在位翻转。

int move(int state, int item) { // item取-1表示不带东西，取0-3表示带对应角色 state ^= (1 << FARMER); if (item >= 0) { state ^= (1 << item); } return state; }

这里用到了异或的一个特性：任何位与1异或，都会翻转；与0异或，保持不变。所以state ^= (1 << FARMER)这一行就只翻转农夫那一位，非常干净。

3. 深度优先搜索的实现要点

3.1 递归框架与visited剪枝

DFS的递归框架几乎是固定的：进入某个状态，标记为已访问，遍历所有可能的下一步动作，如果动作产生的状态合法且没访问过，就继续递归；递归返回后，撤销当前状态（回溯）。

农夫过河问题的visited数组简单得让人感动——总共16个状态，直接用int数组，数组下标就是状态值：

int visited[16];

为什么是16？因为状态是4个二进制位，取值从0到15。数组下标直接对应状态编码，判断是否访问过就是一次数组索引访问，O(1)搞定。

完整框架如下：

int dfs(int state) { if (state == TARGET) { return 1; } visited[state] = 1; // 依次尝试四种动作 int choices[4] = {-1, WOLF, SHEEP, CABBAGE}; for (int i = 0; i < 4; i++) { int item = choices[i]; // 如果要带某样东西，必须保证它在农夫这一侧 if (item >= 0 && is_on_right(state, item) != is_on_right(state, FARMER)) { continue; } int next_state = move(state, item); if (is_valid(next_state) && !visited[next_state]) { if (dfs(next_state)) { // 记录路径 record_path(state, next_state, item); return 1; } } } return 0; // 此路不通 }

这里有个容易忽略的细节：在递归进入下一个状态之前就要做合法性检查，而不是进入后再检查。虽然两种方式最终结果可能一样，但前置检查能少几次无效递归，代码语义也更清楚。

3.2 路径记录与回退

找到目标之后，怎么把路径打印出来？两种做法：

第一种是在递归返回时逐层打印，因为递归栈本身就是路径的逆序。我在找到目标后直接向上层返回，每一层return之前把当前动作记录下来，最终倒序输出。

第二种是用一个path数组，进入新状态时记录，回溯时清除。我比较喜欢第二种，因为它的路径顺序是正向的，调试时更容易对照手动推演。

int path[100]; // 记录每次搜索的下一状态 int path_len = 0; // 在dfs内部，进入某状态前： path[path_len++] = next_state; if (dfs(next_state)) return 1; path_len--; // 回溯时弹出

回溯时减少长度即可，不需要手动清空数组元素，因为后续写入会覆盖。这个小技巧能少写很多代码，也避免了一些新手在回溯时搞错数组下标。

3.3 搜索方向：先带谁过去的细节讲究

DFS的执行结果和动作尝试顺序直接相关。如果先尝试带狼，第一条找到的路径可能是：农夫带狼过去，然后空手回来……但仔细想想，这其实是一条死路，因为把狼带过去后，左岸剩羊和菜——羊会把菜吃掉，非法，直接被is_valid拦住。

我最终选择的动作顺序是：先带羊，然后带狼，然后带菜，最后不带东西。这样第一个被完整探索的可行分支，恰好就是人肉推演时最容易想到的经典解（先带羊过去）。

如果你把顺序改成先带狼、再带羊、再带菜，可能也能搜出解，但路径会绕一些。这里有个经验：DFS找到的第一条路径和动作枚举顺序强相关。想找到“看起来更合理的解”，把直观上安全的动作排在前面；想找到“不同的解”，就要改变枚举顺序。

4. 实操过程与核心环节实现

4.1 从初始状态到目标状态的完整推演

初始化时状态是0（二进制0000），所有角色都在左岸。程序的入口是dfs(0)。

我实际运行时，控制台输出的前10行路径大概是这样的（配合路径打印函数）：

第 1 步：农夫带羊从 左岸 到 右岸 第 2 步：农夫独自从 右岸 到 左岸 第 3 步：农夫带狼从 左岸 到 右岸 第 4 步：农夫带羊从 右岸 到 左岸 第 5 步：农夫带菜从 左岸 到 右岸 第 6 步：农夫独自从 右岸 到 左岸 第 7 步：农夫带羊从 左岸 到 右岸

这条路径正好是手动推演的经典答案：先把羊送过去，空手回来；再把狼送过去，把羊带回来；再把菜送过去，空手回来；最后把羊送过去。

为什么这个路径看起来“很聪明”？因为这七步里面，最关键的一步是第4步——把羊从右岸带回左岸。这一步不是单纯的推进，而是为了把狼和菜互换位置。DFS在这个问题上做得很漂亮，它天然能发现这种“先退回一步再前进”的策略，因为它是深度优先的探索，碰到死路会回溯，回溯不代表失败，而是为了换一条路。

4.2 完整代码实现与关键函数说明

我整理了最终版本的完整核心代码，可以直接编译运行：

#include <stdio.h> #include <string.h> #define FARMER 0 #define WOLF 1 #define SHEEP 2 #define CABBAGE 3 #define START 0 // 0000，全在左岸 #define TARGET 15 // 1111，全在右岸 int visited[16]; int path[100]; int path_len = 0; int is_on_right(int state, int role) { return (state >> role) & 1; } int is_valid(int state) { if (is_on_right(state, WOLF) == is_on_right(state, SHEEP) && is_on_right(state, FARMER) != is_on_right(state, WOLF)) { return 0; } if (is_on_right(state, SHEEP) == is_on_right(state, CABBAGE) && is_on_right(state, FARMER) != is_on_right(state, SHEEP)) { return 0; } return 1; } int move(int state, int item) { state ^= (1 << FARMER); if (item >= 0) { state ^= (1 << item); } return state; } void print_state(int state) { char *pos[2] = {"左岸", "右岸"}; printf("农夫:%s 狼:%s 羊:%s 菜:%s\n", pos[is_on_right(state, FARMER)], pos[is_on_right(state, WOLF)], pos[is_on_right(state, SHEEP)], pos[is_on_right(state, CABBAGE)]); } int dfs(int state) { if (state == TARGET) { return 1; } visited[state] = 1; int choices[4] = {-1, WOLF, SHEEP, CABBAGE}; for (int i = 0; i < 4; i++) { int item = choices[i]; if (item >= 0 && is_on_right(state, item) != is_on_right(state, FARMER)) { continue; } int next_state = move(state, item); if (is_valid(next_state) && !visited[next_state]) { path[path_len++] = next_state; if (dfs(next_state)) { return 1; } path_len--; } } return 0; } int main() { memset(visited, 0, sizeof(visited)); if (dfs(START)) { printf("找到可行路径，共 %d 步：\n", path_len); // 打印每一步的简短描述 for (int i = 0; i < path_len; i++) { printf("状态 %d: ", i + 1); print_state(path[i]); } } else { printf("未找到可行路径\n"); } return 0; }

这个版本省去了一些花哨的输出，核心就三个函数：is_valid做合法性过滤，dfs做深度优先搜索，move做状态转移。实用性很强，你可以直接抄走改一改，就能处理所有“过河类”问题。

4.3 如何验证结果的正误——手动推演与搜索对比

写完代码之后，验证是最重要的一步。我每次验证这类搜索代码都会做两件事：

第一，把程序找到的路径一条一条手动推演一遍，模拟每个状态是否合法。比如第2步从“农夫右岸、狼左岸、羊右岸、菜左岸”变到“农夫左岸、狼左岸、羊右岸、菜左岸”，此时左岸有农夫、狼、菜，农夫在场，安全；右岸有羊，孤零零一只羊，也安全。

第二，把visited打出来看看到底走了哪些状态。因为总共就16个状态，全打印出来也就几行，对照着看，你会很清楚搜索有没有遗漏。

我在调试时还试过几种变体，比如去掉is_valid中的羊菜判断，程序果然会输出一条“羊吃菜”的非法路径。这种反向验证很有用，能帮你确认每个过滤条件都是必需的。建议你拿到代码后在本地做一次这样的实验，比单纯看代码理解深刻得多。

5. 常见问题与排查技巧实录

5.1 为什么程序会陷入死循环

我在带新人做这道题时，最常见的问题是程序一直跑不出来，加打印后发现它在两个状态之间反复横跳：农夫带羊过去、农夫带羊回来、农夫带羊过去……形成了环路。

原因很简单：没有visited剪枝，或者visited标记的位置不对。如果只在进入递归后标记，回溯时又立即撤销标记，那么两条不同路径可以经过同一个状态，这本来没错，但问题是会形成无限循环。

更好的做法是：在当前这条搜索路径上，已访问过的状态不能再进。这个“路径上的已访问”和“全局的已访问”是两回事。

农夫过河问题由于每个状态最多被真正“完整探索”一次就够了，所以我用全局visited数组，进入一个状态后置1，之后无论从哪条路径再来都不再进入。回溯时也不需要清0，因为如果当前状态已经被完整探索过且没有找到解，说明从这个状态出发的所有路径都走不通，下次再遇到这个状态也没必要重新探索。

如果你改造成“路径去重生效”的需求，那就是另一类问题了，比如全排列、迷宫寻路中要求不重复走格子。那种场景visited必须在回溯时清0。理解这两者的区别很重要。

5.2 搜索到了路径但不是最短路径，正常吗

正常。深度优先不保证找到最短路径，这是它的特性，不是Bug。很多时候你第一次找到的路径就是“当前动作枚举顺序下的第一条可行解”，不是全局最优。

我试过调整动作顺序，把“带狼”放在最前面，程序找到了另一条路径，步数更多，大概9到11步，路径也很合法，只是绕了远路。这就是DFS的特点：找到什么解，取决于先往哪个方向深入。

那如果你的实际需求必须是最短渡河方案呢？解法是用BFS，宽度优先搜索第一次到达目标状态时，路径就是最短的。为了训练理解，我建议你把两种实现都写一遍，对比输出结果。这个对比会让你直观感受到DFS和BFS在路径长度上的差异。

5.3 visited数组容量怎么确定——不要拍脑袋定大小

我见过有同学上来就写int visited[10000]，这个倒是不会出错，但不够优雅。正确做法是先分析状态空间规模，再定数组大小。农夫过河问题里，每个角色要么左岸要么右岸，四种角色，所以状态总数是2的4次方等于16个。数组大小16就够了。

很多“过河类”问题的变体（比如传教士和食人族问题）状态数量也有限，公式就是状态数等于每个个体的位置可能数相乘。先用数学把状态空间算清楚，再定数组大小，这是建模能力的体现。

5.4 调试技巧：如何快速定位搜索逻辑错误

我调试这类递归代码有一个固定的套路：打印“进入状态 / 退出状态”的日志，缩进对齐，一眼就能看出搜索树的形状。

void print_space(int depth) { for (int i = 0; i < depth; i++) printf(" "); } int dfs(int state, int depth) { print_space(depth); printf("进入状态 %d\n", state); ... print_space(depth); printf("退出状态 %d\n", state); }

一旦看到某个状态反复进出，或者搜索树突然断在某个分支，基本就能锁定问题。这个思路不止适用于农夫过河，任何DFS题目调试都用得上，算是一个通用方法论。

6. 从农夫过河到更广阔的搜索世界

6.1 同一个框架能解决哪些问题

把这个问题吃透之后，你会发现它的本质是“有限状态空间中的路径查找”。只要能把问题抽象成“状态 + 动作 + 合法性约束”，这套DFS框架就能直接迁移。

典型的例子包括：八数码问题（华容道类）、迷宫求解、传教士与食人族、汉诺塔的移动步骤，甚至更复杂的八皇后问题，用的都是完全一样的回溯+剪枝框架。差别只在于“状态定义”和“动作生成逻辑”不同，搜索主体结构几乎原封不动。

我举个例子：传教士与食人族问题是三个人和三个食人族要过河，船最多坐两个人，而且无论在哪一岸，食人族都不能比传教士多。状态变成6个角色的位置组合，动作变成枚举所有可行的船上组合。核心代码的DFS递归部分一点都不用改，只要替换掉状态建模、合法性判断和动作生成就够了。

6.2 深挖很值得：从DFS到回溯法再到记忆化搜索

如果顺着农夫过河往下走，很自然的下一步是回溯法解题——那些需要“尝试所有可能组合”的题目，比如组合求和、全排列、分割回文串，本质都是DFS加上收藏/撤销路径的过程。

再往前走一步，如果某个状态会被重复计算很多次，就可以在DFS框架上加缓存，把计算结果存起来，这就是记忆化搜索，也叫做递归形式的动态规划。前面提到visited数组其实已经有点这个味道了——它缓存的是“这个状态探索过没有”，而记忆化搜索缓存的是“这个状态的计算结果是什么”。

所以，千万别觉得农夫过河只是道脑筋急转弯。它是一扇门，推开后通向的是整个搜索算法家族。我在面某家公司的时候，面试官就是从这道题开始，一路问到记忆化搜索和动态规划的优化，前后聊了四十分钟。把基础打扎实，后面都是顺水推舟的事。

6.3 动手改造建议：从这五个方向加深理解

如果你想把这道题的价值榨干，我建议你按这几个方向逐一改造代码：

第一，把DFS改成BFS，输出最短路径，对比两条路径的步数差异。第二，在DFS里加一个参数限制最大深度，看看当深度小于某值时是否无解，理解迭代加深的思想。第三，修改动作枚举顺序，观察输出路径的变化，理解枚举顺序对结果的影响。第四，把状态输出为中文描述，做成一个完整可交互的控制台程序。第五，尝试把问题推广成“多一个角色”或“船能坐两个人”，看看状态空间和判断逻辑怎么改。

我实际带过一个小组，有人把这题改成了“三个人三只怪兽过河”，还加了一个“船必须有人划”的限制，最后整个小组对状态搜索的理解水平明显高出一截。动手改造永远是最快的学习方式。