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

让我们来看之前讲广度优先搜索时用到的例图。重申一遍：图是由点和连接点的边组成的数据结构。它们可以用来表示很多不同的概念：比如城市地图、网络结构、犯罪团伙的网络，甚至是一个城堡的建筑结构。我们从Kingdom HighwayMap中的案发城市——A城市——来开始搜索。

深度优先搜索会沿着一条路探索下去，直到它遇到一条死路（或者一个之前已经探索过的状态）。也就是说，深度优先搜索优先考虑的是搜索的深度，而不是广度。

和之前一样，我们在H城找到了罪犯。不过这一次我们在搜索过程中走了一条不太一样的路径。

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