11 废弃监狱中的深度优先搜索（第2/3页）

“现在我们退回上一个经过的房间，5号房间，那里面的霉菌形状像马一样。”当他们倒退回去的时候，Frank这样解释道。这次，他们选择了5号房间内唯一还没走过的方向——西边。不幸的是，他们立刻就遇到了另一个死路——一个空房间，里面有一堆像花的形状的蓝色和绿色绒毛状霉菌。

由于刚刚经过的房间的所有选项都已经尝试过了，他们继续倒退，回到了4号房间。4号房间的东边是死路，而北边他们已经走过了，于是这次他们走了南边。

他们走过了8号和9号两个空房间。这两个房间唯一的区别就是里面那一大团像钟乳石一般的霉菌的形状。Frank和Socks走过的时候，都下意识地和那团霉菌保持着距离，因为那团霉菌看起来随时都会坍塌。在又一次遇到死路后，他们只能连续倒退到了2号房间。

“我们会不会已经走过了？”Socks问道，语气还是一如既往地忧心忡忡，“或者会不会我们迷失在一个环中了？会这样一直无限走下去？”

Frank哼了一声：“年轻人，这不是我第一次做深度优先搜索了。跟着我做就没错的。”

“但不会有环吗？”

“你想想我为什么要在墙上做记号？”Frank问道，“如果我们不重复经过已经做过记号的墙上的门，我们就不会困在环中。”

Frank是在一次警用算法课的练习中学会这样做的。在那次练习中，Frank在全班的注视下绕着竹篱做的迷宫内的一个环走了六次。旁观的一个同学甚至大声开玩笑说：“看，他又走了一次！”

他们继续沿着一条曲折的路线向迷宫深处探索，时不时在遇到死路时倒退几步。

然后，他们在23号房间里找到了一个装着羊皮纸和一堆笔记本的盒子。

“我们找到了！”Socks激动地说道。一不小心，他的法杖底端射出了一道闪烁的蓝光。

Frank被这堆纸的数量之多吓了一跳。在警察局这么多年来，Frank在长官的要求下处理过的公文数量繁多，不过那些和眼前的这些纸比起来根本不算什么。而且最底下的几张纸上还有霉菌的印记。整件事都不太对劲。

Frank走向离他最近的一堆羊皮纸，从中拿出了一张。纸上的标题写着《关于鸭圈栏杆正确使用方法的公告》。上面的时间和所属警察局的编号证明这份文件的确是那些被偷的文件之一。下一张纸上写着所有West Serial港口内关于噪声污染的投诉诉状，同样也是被偷的文件之一。不过这两份文件对现在进行的调查而言都几乎没用。

Frank跪下来，从这堆纸的底部拿出一本笔记本。笔记本内页上沾着三块霉菌斑点，不过还是可以清楚地看到上面写的是给城堡护卫的补给品清单，可以断定这个笔记本本来就是这座城堡里面的。Frank又拿出了一本笔记本，上面写着的是去年11月份城堡护卫的轮班日程。

“这不对劲，”Frank低声说道，“这里的文件太多了，还有好多城堡内的笔记本。”Frank换到旁边的另一摞，再次从最上面开始查看。

“这些文件有规律吗？”Socks问道，听起来好像刚刚意识到眼前的文件有多少。

“我……”Frank说道，不过说到一半停住了，开始翻看另一本标题为《转账申请》的笔记本。笔记本中有四页被撕掉了。

“真奇怪，”Frank边翻看着那些没被撕掉的纸页边说道，“这些也许是……”

突然Socks失去了平衡，倒向了Frank，打断了他正在说的话。Frank注意到黑暗中有些动静。这时，Frank听到门上的链子发出了尖锐的声音。Frank这才意识到发生了什么。

“门那里！”Frank在Socks快要倒在他身上的时候叫道。

两人倒在了地上，门砰的一声关上了。随着咔嚓一声，门锁上了。Socks的魔杖在这片混乱中掉到了地上，滚进了一个干的羊皮纸堆里。魔杖顶端发出了一团比之前大得多的蓝色火焰。

Frank坐在地上，震惊地看着那堆纸被点燃。

警用算法导论：深度优先搜索

节选自Drecker教授讲义

与广度优先搜索不同的是，深度优先搜索会优先考虑最近新遇到的搜索状态。所以算法会沿着一条路往下走，直到遇到目标状态，或者一条死路。

和广度优先搜索一样，在使用深度优先搜索时，也可以去维护一个列表（更准确地说，是一个栈），里面存放着所有已知但还未探索过的状态。每一步，算法都会从栈的顶端选出下一步要去探索的状态。但与广度优先搜索不同的是，深度优先搜索会将新的状态加到栈的顶端，而不是尾部。