进了监狱，刚走了两步，Frank就意识到他们走进了一个迷宫。曾几何时，这些计算型监狱几乎都不需要警卫，而是完全依靠自身结构的复杂与怪异去关住里面的犯人。那些想逃跑的犯人在付诸行动前都会三思：他们甚至都不知道溜过面前的这扇门后，等待着自己的会是自由，还是警卫的休息室。
“来点光吧？”Frank提议道。
“哦，对哦！”Socks回应道。他低声念了一个咒语，一团蓝色的光从他法杖的一端亮了起来，照亮了他们所在的毫不起眼的房间。
房间是正方形的，四周是粗糙的石墙，和几扇栎树木做的房门。环顾四周后，Frank愈发确信了自己的猜想：整个监狱是由很多网格状排列的房间组成的，而每间房内的一些墙上则有通向相邻房间的门。他们需要一间一间地找。但由于他们并不知道哪些房间之间门相连，所以他们必须得走一步看一步地搜索下去。
“看来是时候再来一次搜索了。”Frank说道。
“搜索？”Socks问道，“搜索什么？”
“当然是那些纸了。”Frank回答道。他确信那些纸一定是被藏在了这里。相比一般人用的仓库，一个废弃监狱毫无疑问是藏偷来物品的更好场所。当然，如果能找得到一座有护城河的城堡的话，那可能会更理想一点。现在的问题就是他们能否在这里找到那些纸，以及找到之后能不能从中得到任何有用的线索。
“千万别再来个广度优先搜索了。”Socks抗议道。
Frank考虑了一番。理论上，在一个网格状的监狱上用广度优先搜索没什么问题。每一个格子便是一个搜索状态，而每当你探索过一个格子后，就可以把与之相邻的尚未被探索的格子加到你的搜索列表中。Frank在头脑中想象出了整个搜索过程，就像水面上的水波逐步扩散的过程。
不过，如果把广度优先搜索用在现实生活中，比如在一栋建筑物里搜索，就会有一个很严重的问题，那就是会引起大量的倒退。由于每次都是将新的搜索状态加到列表的最后，所以需要探索的下一个状态可能离你特别远。即使在一个没有墙阻挡的空网格上，你也需要走相当长的一段距离才能抵达下一个状态。
而Frank正是不想走这样没有用的路。
“不，”Frank说道，“需要太多次倒退了。我们最好用深度优先搜索。”
“深度优先搜索，深度优先搜索，”Socks不断地对自己重复着这个词，像是在试图把它印在脑中似的，“我好像不记得……”
Frank对他挥了挥手，自信地向走廊深处走去。他说道：“我们不需要用咒语来做这个。当你还是个用纸尿裤的婴儿时我就已经在做这套深度优先搜索了。”
“所以用深度优先搜索不需要倒退了？”Socks问道。
“绝大多数搜索算法都会需要倒退。不过深度优先搜索中的倒退更适合人来走。”
“哦，我明白了。”
“不，你并不明白，”Frank毫不留情地说道，“如果你不懂这个算法的话，问就是了。不懂装懂只会给你自己带来麻烦。我见识过太多新手警察在搜索上栽跟头了，和你一样的新手。”
“好吧。那什么是深度优先搜索？”Socks问道。
“它是一个很简单的算法，”Frank解释道，“简单来说，我们就是沿着每条路往深处走，直到遇到一条死路。而当遇到死路后，我们就倒退一步，找到我们还没有走过的另一条路走下去。如此反复，直到找到我们的目标为止。
“现在我们就按顺时针的顺序开始吧。当我们有多个选择时，我们就按北→东→南→西的顺序来走，当然我们需要跳过之前已经走过的路。在每一个路口我们都按同样的顺序来选择方向，所以我们在能够向北走的时候总会优先向北走。不过现在，我们只有一个选择，那就是往南走。”
Frank正说着，他们就走到了第一个需要做决定的房间。Frank思考了一下他们可以走的方向：由于他们是从北边来的，不能往回走，所以Frank选择了顺时针顺序中的下一个方向：东边。在走出这间房之前，Frank从口袋中拿出了一支粉笔，在墙上做了一个记号。
又经过了两个分叉口，向北又向东之后，他们遇到了第一个死路。到目前，他们走过的房间要么是完全空着的，要么只有一个监牢。由于没有任何其他可以用来分辨房间的特征，Frank在每个房间的墙上都写上了一个不同的数字。而在Frank的头脑中，他已经将这些数字与它们所在房间里面霉菌的形状联系在了一起。
“现在我们退回上一个经过的房间，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教授讲义
与广度优先搜索不同的是，深度优先搜索会优先考虑最近新遇到的搜索状态。所以算法会沿着一条路往下走，直到遇到目标状态，或者一条死路。
和广度优先搜索一样，在使用深度优先搜索时，也可以去维护一个列表（更准确地说，是一个栈），里面存放着所有已知但还未探索过的状态。每一步，算法都会从栈的顶端选出下一步要去探索的状态。但与广度优先搜索不同的是，深度优先搜索会将新的状态加到栈的顶端，而不是尾部。
让我们来看之前讲广度优先搜索时用到的例图。重申一遍：图是由点和连接点的边组成的数据结构。它们可以用来表示很多不同的概念：比如城市地图、网络结构、犯罪团伙的网络，甚至是一个城堡的建筑结构。我们从Kingdom HighwayMap中的案发城市——A城市——来开始搜索。
深度优先搜索会沿着一条路探索下去，直到它遇到一条死路（或者一个之前已经探索过的状态）。也就是说，深度优先搜索优先考虑的是搜索的深度，而不是广度。
和之前一样，我们在H城找到了罪犯。不过这一次我们在搜索过程中走了一条不太一样的路径。
和广度优先搜索一样，我们也会记录下已经探索过的点。这样就可以避免重复探索一个点，这在图里可能有环的时候格外重要。如果不记录的话，你可能会陷入一个环中，无穷无尽地沿着这个环重复探索上面的状态。在上图所示的例子中，我们通过记录下探索过的点来避免将之前已经加入过列表的点（无论它有没有被探索过）再次加入列表。