進了監獄，剛走了兩步，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城找到了罪犯。不過這一次我們在搜索過程中走了一條不太一樣的路徑。
和廣度優先搜索一樣，我們也會記錄下已經探索過的點。這樣就可以避免重複探索一個點，這在圖裡可能有環的時候格外重要。如果不記錄的話，你可能會陷入一個環中，無窮無盡地沿著這個環重複探索上面的狀態。在上圖所示的例子中，我們通過記錄下探索過的點來避免將之前已經加入過列表的點（無論它有沒有被探索過）再次加入列表。