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

然后，他们在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城找到了罪犯。不过这一次我们在搜索过程中走了一条不太一样的路径。

和广度优先搜索一样，我们也会记录下已经探索过的点。这样就可以避免重复探索一个点，这在图里可能有环的时候格外重要。如果不记录的话，你可能会陷入一个环中，无穷无尽地沿着这个环重复探索上面的状态。在上图所示的例子中，我们通过记录下探索过的点来避免将之前已经加入过列表的点（无论它有没有被探索过）再次加入列表。