13 用栈和队列搜索

Frank努力将烧焦面包的画面从脑海中消除,重新将注意力集中到他们目前的处境。他们现在被困在一间房间里,里面装满了即将燃烧起来的羊皮纸。火势目前还很小,只烧到了那一摞纸最边上的几张散页。但是一旦那一摞纸燃烧起来,火势将无法控制。

Socks爬向门的方向,随后将身体靠在门上。“它锁住了吗?”他问道。

Frank心中想到了无数嘲讽Socks的方式,但最终他只是简单地点了点头。“你能打开它吗?”他问道,“这是一个老式的两针式的锁,不会有太多种组合方式的。”

Socks摇了摇头。“没时间了。不过我知道一个软化铁的咒语。当然用了它这个门就彻底毁了。不过当下这种情况,门的好坏已经无所谓了。”

他拿起自己的魔杖,立刻开始行动。他念着咒语,手不断在门上游走。他的手经过的地方逐渐长出了铁锈,很快就铺满了这个铁门的表面。不到一分钟后,Socks退后了一步。铁门看起来已经锈透了,但不管怎么说,毕竟还是铁做的。

“铁门现在应该比之前要脆弱很多了,”Socks说道,他又后退一步,期待地看着Frank,仿佛在说:“现在你随时可以直接破门而出了。”

Frank也退后几步,两眼打量着那扇门。“有多脆弱?”Frank问道,“你说的脆弱是像牙签那样,还是像一块厚木板那样?”

“额……肯定比一般的铁脆弱多了,”Socks回答道,“我让它多了很多铁锈。虽然门很厚,但我想它现在应该相当脆弱了。”

Frank低吟了一声,他深呼吸了一下,积蓄着力量。然后,他放低自己的肩膀,冲向了门。撞上的那一下Frank的整个身体都震了一下,但他终究还是冲过去了。

冲过门的Frank四肢张开地躺在地上,而他四周的空气中已充满了铁锈。

Socks急忙跑到他身边。“你还好吗?”他回头望了门一眼,随即笑道,“成功了!”他骄傲地说道,“门是不是很脆弱?撞上去的感觉如何?”

“像撞一尺厚的木头一样,”Frank说道,“疼死了。”

Socks脸上的笑容暗淡了一些,说道:“哦……”

Frank努力站起来,肩膀非常疼,明天那里肯定会淤青一大片。但目前,和逃离火海的开心相比,那些都不算什么。

“该走了。”Frank一边走向下一个房间,一边说道。

“你还记得怎么回去吗?”Socks问道。

“当然,”Frank回答道,“我们是用深度优先搜索找到这里的。我们沿着栈回去就好了。”

“栈?”Socks边跟上Frank边问道。

“对,”Frank一边在心中回味着刚刚的逃脱,一边回答道,“我们可以用不同的数据结构来区别这两种不同的搜索。比如,广度优先搜索用的是队列,而深度优先搜索用的则是栈。”Frank此时竟然给出了教科书般的答案,简直像Notation附体了似的。

“实际上,在进行深度优先搜索的时候,有很多种可以用栈来记录目前选项的方法。有些人喜欢用栈来记录下一列他们还未探索过的房间,就像你在广度优先搜索中用的队列一样。但我喜欢用另一种方法。

“你可以用一个栈来存放你当前走过的路径上的房间。每当探索到一个新房间时,就将它推入到这个栈中。

“当你倒退时,就将那个房间从栈中推出,并回到它之前的那个房间。这样,你永远都能知道如何倒退回起点。为了让倒退的过程容易些,我还将房间都编了号。”

“我以为只要每次回到我们之前最后一个需要做决定的分叉口就行了。”Socks说道。

“其实就是这样,”Frank说道,“但是将目前路径上的房间放在一个栈里可以让这样的做法变得更容易。你只要不断地倒退,并将房间从栈中推出,直到你倒退到一个还没有完全探索完的房间为止。”

Socks看起来十分佩服Frank,说道:“你把我们探索过的房间都写下来了?”

“我把那个栈记在脑中,并且用粉笔对房间都编过号了,”Frank回答道,“我之前说过,这不是我第一次用深度优先搜索了。我们需要倒退七个房间。”

他们匆忙地跑过了两个黑暗的房间。Socks突然想起手中的魔杖。随着他低吟着点火的咒语,他手中魔杖的顶端冒出了一团蓝色火焰。

Frank紧张地看了眼魔杖。“把它握紧一些。”他说道。

又走过了三个房间后,Socks突然问道:“那队列呢?”

“队列怎么了?”Frank问道。