A.3 搜索算法基础 DFS、BFS与回溯

1.开场：搜索是计算机科学的看家本领

说起来，深度学习这一路学下来，大家应该也慢慢习惯了吧，把问题建模成计算图（3.2 节里我们讲过，一张网络其实就是有向图，节点是运算，边是数据流向）。可把问题画成图只是第一步，真正要解决它，往往还得在这张图里头走来走去地找东西。从某个起点出发，沿着边一步步走，直到找到目标，这件事在计算机科学里有个专门的名字，叫搜索。搜索算法算是这门学科的看家本领，路径规划、游戏AI、数据库查询、编译器优化，到处都能见到它的影子。3.1 节讲图论的那部分（还在整理，将来会补上）其实也是为这里做铺垫，图论给了我们描述状态空间的语言，而搜索算法教我们怎么在这片空间里头走得又稳又快。今天这一篇我们先打基础，讲三种最经典的套路，广度优先搜索BFS、深度优先搜索DFS，以及在DFS上头长出来的回溯(backtracking)。

2.BFS：像水波一样一层层往外扩

我们先从最好理解的一种讲起，BFS（Breadth-First Search，广度优先搜索）。它的样子有点像往平静的湖面投一颗石子，水波从落点一圈圈往外推，越扩越远。落在搜索这件事上呢，BFS说的是从起点出发，先访问所有和起点直接相邻的节点，再访问和这些节点相邻、但还没访问过的节点，就这样一层一层地往外推，直到把能到的地方都走遍。这种走法天然有个好处，就是它能保证先被访问到的地方步数少。原因也不难想，我们按距离起点的远近顺序依次访问，离起点近的节点一定先被碰到。在一张边上不带权的图里（每条边走过去的代价都一样，记作1），这种性质正好对应最短步数。

实现BFS要用到一种数据结构，叫队列(queue)。什么叫队列呢，它是一种先进先出的结构，先排进去的先被取出来处理，就像食堂打饭排队那样，先来的先打到饭。我们维护一个队列，每次从队首取出一个节点，把它所有还没访问过的邻居依次塞到队尾，同时给这些邻居标上已访问。这样下一个被处理的节点，永远是当前这一层里最早入队的那一个，整个访问顺序就严格地按层推进。

这里要引出一个衡量开销的概念，叫时间复杂度。我们用V来表示图里所有节点的总数目，用E来表示图里所有边的总数目。BFS跑下来，每个节点最多入队一次，每条边最多被扫两遍，所以总工作量和图的规模成正比，时间复杂度记作O(V+E)。其中O是一种刻画增长趋势的数学记号，括号里的式子告诉我们图的规模变到多大时算法最多要花多少时间，V+E的意思就是节点数和边数一起决定了工作量。

讲个具体的小例子。小明同学要从学校西门去图书馆，校园里几条路连成一小张图。节点A是西门，节点B是食堂，节点C是教学楼，节点D是图书馆。A和B之间有路，A和C之间也有路，B和D之间有路，C和D之间也有路。我们想算A到D最少要走几步，BFS的过程大概是这样。第一步，把A入队，标上已访问。第二步，从队首取出A，发现它有邻居B和C都没访问过，于是把B和C依次塞进队尾，并记下它们离起点的距离都是1。第三步，取出B，它的邻居里D还没访问，把D入队，距离记作2。第四步，取出C，发现D已经被B报过访问了，就跳过。第五步，取出D，正好是目标，搜索结束。答案是2步，跟直觉一致。

换一个更生活化的场景。比如坐地铁换乘，你想知道从1号线某站到目的地最少要换几次车，BFS也是最趁手的工具。把每条线路相邻两站看成一条边，换乘站把不同线路串起来，按层往外扩，第一次摸到目的地时坐过的线路数，就是最少换乘。很多城市的地铁App算换乘方案，底层就靠这种思路。

3.DFS：一条路走到底再回头

DFS（Depth-First Search，深度优先搜索）的脾气和BFS正好相反。它的走法是认准一个方向一路扎到底，走到没路可走了再回头换条路试。说起来像探险，我之前翻过一本讲迷宫的旧书，里头提到有些迷宫的老式解法就是顺着一只手摸着墙走，摸到死胡同就掉头换边，这种一根筋的走法和DFS颇有几分神似。

实现DFS通常有两种写法。一种是用递归，进入一个节点就先访问它，然后随便挑一个没走过的邻居往下钻，递归调用自己。另一种是用栈(stack)，栈是后进先出的结构（最后放进去的最先被取出来），手动把要访问的节点压进栈里。两种写法本质一样，都体现了走到底再回头的思想。DFS不像BFS那样按层推进，所以它没法直接保证找到的路径最短，可它有另外的长处。一是省内存，只需要记当前这条探索路径上的节点。二是适合做整张图的遍历，找连通块、判断有没有环、做拓扑排序都靠它。

我们也手动走一遍小例子吧。还是上一节那张小图，A、B、C、D四个节点。DFS从A出发，先访问A，然后挑一个邻居往下走，假设先挑B，访问B，再从B往下走，访问D。这时D已经没有没访问过的邻居了，回退到B，B也没别的邻居可走，再回退到A。这时A还有邻居C没走过，于是访问C，C的邻居都走过了，再回退到A，整个遍历结束。访问序列就是A、B、D、C。和BFS那层层铺开的稳重相比，DFS明显更激进，喜欢一口气扎到底。

DFS的时间复杂度同样是O(V+E)。每个节点最多被访问一次，每条边最多被扫两次，开销和图的规模成正比。

我再讲一个DFS特别常见的用处，叫找连通块。连通块说的是图里彼此能相互到达的一组节点。比方说社交网络里一群人彼此都通过朋友关系连得上，就把他们看作一个连通块。我们用DFS遍历整张图，遇到一个还没访问过的节点，就启动一次新的搜索，把从它能到达的所有节点都访问一遍，这一次搜索摸到的全部节点，就是一个连通块。这样扫一遍下来，整个图就被切成几个连通块了。小明做毕设那会儿调社交网络数据，想看看用户分成了几个圈子，用的就是这个套路。

4.回溯：在DFS上头长出撤销这一手

回溯(backtracking)是搭在DFS骨架上的一种技巧。它的核心是把搜索过程组织成一棵搜索树，从根节点出发，每一个内部节点都代表一次选择，每一条走到叶子的路径就是一个候选解。回溯和普通DFS最大的区别在于，它会主动撤销之前做过的选择，回到上一层去试别的可能。这种撤销的机制，让它可以系统地穷举所有可能的解。回溯这个名字本身就点明了意思，走了就回溯，回头再试别的。

回溯的代码骨架非常规整，几乎可以套公式。我们写一个递归函数，参数里带着当前走到了哪一步，以及到目前为止已经做过的选择。函数体里通常是三步：第一步选择，从当前可选的选项里挑一个，把它加到当前路径上。第二步递归，进入下一层继续选。第三步撤销，把刚才加进去的选择再拿出来，恢复原状，好让下一次循环能干净地试下一个选项。这三步循环往复，就把所有可能的解都遍历了一遍。我把这个套路叫作选择、递归、撤销。

经典例子首推八皇后。棋盘8行8列共64个格子，要放8个皇后，要求任意两个皇后都不在同一行、同一列、同一对角线上，问有多少种摆法。我们一行一行地放，每行挑一个合法的列号，挑完了就递归到下一行。要是发现某一行哪个列号都不合法，说明前面这次选择走不通，就退回去换上一行的列号再试。把所有能走通的路径都记下来，最后答案就是92种合法摆法。这个92不是猜的，是程序老老实实回溯一遍数出来的。我记得看过一部讲程序员的电影，里头女主角面试就被考到八皇后，可见这题在算法面试里头地位不低。

还有一个更直观的例子是全排列。给定三个数字1、2、3，要列出所有可能的排列。我们从空序列开始，第一个位置可以先放1，递归到下一个位置，从剩下的2和3里挑，假设先挑2，再递归，最后只剩3，得到一组排列1、2、3。然后回溯，把3拿掉，发现没有别的可选，再回溯把2拿掉，这次改挑3，又得到1、3、2。再回溯到最外层，把1拿掉，改挑2开头，重复同样的过程，最终能得到全部6种排列。整个过程就像一棵树在系统性地长枝丫，每一根枝丫末梢就是一个完整的解。

回溯里头还有一手特别要紧，叫剪枝(pruning)。朴素的回溯会把搜索树的所有分支都走一遍，可很多时候某些分支一开始就明显走不到合法解，再往下钻纯属浪费时间。剪枝就是提前判断出这些没希望的分支，直接砍掉，不再深入。举个例子，数独这种游戏，要是某个空格连一个合法的数字都填不进去，说明前面填的某个数字有问题，这一整条分支就不必再试，立刻回退。剪枝的好坏往往决定一个回溯程序能不能在合理时间里跑完。有些问题不剪枝要算到天荒地老，剪得好几秒钟就出结果。这种差距其实也好理解，搜索树是指数级膨胀的，每砍掉一层，工作量就缩水一大截。小张去年参加算法竞赛，就因为少写了一处剪枝，一道回溯题硬是超时没过，事后懊恼了好几天。

5.三者对比：什么场景用什么招

最后我们把三者的脾气梳理一下，方便大家选的时候心里有数。

BFS找的是无权图里的最短步数，这是它最大的优势。代价是它得把整层节点都同时记着，内存占用比较大。一个典型的应用场景是迷宫最短步数，游戏里格子地图上算角色走到目的地最少几格，地图规模一大，队列里同时挤着的节点就非常多。

DFS的优势是省内存（只记当前路径），适合做整张图的遍历、找连通块、判断有无环、做拓扑排序这些活。代价是不保证找到的路径最短。一个典型的应用场景是迷宫里判断能不能走出去（只问通不通，不问多短），或者在一棵文件目录树里找某个特定文件。

回溯专门对付组合搜索和排列枚举这种问题。八皇后、全排列、数独、子集和、组合枚举都靠它。代价是搜索树指数级膨胀，不剪枝的话规模稍大就跑不动。

说穿了，这三种套路并非互相排斥，很多实际问题里要混着用。比方说走迷宫既要找最短步数又要在某些约束下回头试别的路径，可能就要BFS搭回溯一起上。还有一种更进阶的搜索思路，像Dijkstra算法、A*算法，专门处理边上带权的最短路径，留到下一讲细说。再有遗传算法、模拟退火、粒子群PSO、蚁群ACO这些启发式方法，专门对付TSP（旅行商问题）这种状态空间大到爆炸的NP难题，它们用适应度函数或者信息素这类机制做近似搜索，思路和本篇讲的精确搜索完全不同，等以后专门写一篇再聊。

搜索这一块今天就先讲到这儿，下一章我们讲带权最短路径，回见。

练习

Q1. BFS和DFS分别用什么数据结构实现？为什么BFS能保证无权图里找到最短步数，而DFS不能？

BFS用队列（先进先出）实现，DFS用栈或递归（后进先出）实现。BFS能保证最短步数是因为它按距离起点的远近顺序一层层访问，离起点近的节点一定先被碰到，所以在无权图（每条边代价都一样记作1）里第一次摸到目标时走过的步数就是最少的。DFS认准一个方向一路扎到底、走不通再回头，不按层推进，所以它没法保证找到的路径最短，只保证能找到一条。

Q2. 回溯算法的代码骨架通常有哪三步？请以全排列（列1、2、3所有排列）为例说明。

三步是"选择、递归、撤销"：第一步选择，从当前可选选项里挑一个加到当前路径上；第二步递归，进入下一层继续选；第三步撤销，把刚才加的选择拿出来恢复原状，好让下一次循环干净地试下一个选项。以全排列1、2、3为例：第一个位置先选1，递归到下一位置从2、3里挑，假设挑2再递归只剩3，得到1、2、3；然后撤销3、再撤销2改挑3，得到1、3、2；再回溯到最外层撤销1改挑2开头，重复同样过程，最终列出全部6种排列。

Q3. 易错点：回溯里的"剪枝"是不是可有可无的优化？为什么有些问题不剪枝会"算到天荒地老"？

不是可有可无，常常是能不能在合理时间里跑完的关键。朴素的回溯会把搜索树所有分支都走一遍，可搜索树是指数级膨胀的，很多时候某些分支一开始就明显走不到合法解（比如数独某空格连一个合法数字都填不进），再往下钻纯属浪费时间。剪枝就是提前判断出这些没希望的分支直接砍掉、不再深入。每砍掉一层工作量就缩水一大截，剪得好几秒出结果、不剪可能算到天荒地老。所以剪枝的好坏往往决定一个回溯程序能不能过，不是锦上添花而是雪中送炭。