第40章：深度优先搜索

在上一章中，你看了广度优先搜索（breadth-first search，BFS），在这一章中，你必须先探索一个顶点的每一个邻居，然后再进入下一层次。在本章中，你将了解深度优先搜索（DFS），这是另一种用于遍历或搜索图形的算法。

DFS有很多的应用。

• 拓扑排序。

• 检测一个周期。

• 寻路，例如在迷宫游戏中。

• 寻找稀疏图中的连接部件。

为了执行DFS，你从一个给定的源顶点开始，试图尽可能地探索一个分支，直到你到达终点。在这一点上，你会回溯（后退一步）并探索下一个可用的分支，直到你找到你要找的东西或你已经访问了所有的顶点。

例子

让我们来看看DFS的例子。下面的例子图与前一章相同。这是为了让你看到BFS和DFS之间的区别。

你将使用一个堆栈来跟踪你所移动的层次。栈的后进先出方法有助于回溯。栈上的每一次推送都意味着你向更深的层次移动。如果你走到了死胡同，你可以跳出来回到上一层。

1. 像上一章一样，你选择A作为起始顶点，并将其加入堆栈。

2. 只要堆栈不是空的，你就访问堆栈上的顶点，并推送第一个尚未访问的相邻顶点。在这种情况下，你访问A并推送B。

回顾上一章，你添加边的顺序会影响搜索的结果。在本例中，第一个加到A的边是加到B的边，所以B先被推到。

3. 你访问了B并推了E，因为A已经被访问了。

4. 你访问了E并推了F。

请注意，每次你在堆栈上推送时，你都会在一个分支上前进得更远。你不是访问每一个相邻的顶点，而是继续沿着一条路径前进，直到到达终点，然后回溯。

5. 你访问了F并推了G。

6. 你访问G，然后按C。
   

7. 下一个要访问的顶点是C，它有邻居[A, F, G]，但所有这些都已经被访问过了。你已经走到了一个死胡同，所以现在是时候通过从堆栈中弹出C来进行回溯了。

8. 它有邻居[F, C]，但所有这些都已经被访问过了。另一个死胡同，弹出G。
   

9. F也没有未访问的邻居了，所以弹出F。

10. 现在，你回到了E，它的邻居H还没有被访问，所以你把H推到堆栈上。
    

11. 访问H的结果是另一个死胡同，所以推掉H。

12. E也没有任何可用的邻居，所以弹出它。
    

13. B的情况也是如此，所以弹出B。

14. 这让你一路回到了A，他的邻居D仍然需要被访问，所以你把D推到堆栈上。
    

15. 访问D的结果是另一个死胡同，所以弹出D。

16. 你又回到了A处，但这一次，没有可用的邻居可以推，所以你推掉了A。

在探索顶点时，你可以构建一个树状结构，显示你所访问的分支。你可以看到与BFS相比，DFS走得有多深。

实现

打开本章的启动游戏场。这个操场包含一个图形的实现，以及一个堆栈，你将用它来实现DFS。在你的主操场文件中，你会注意到一个预先建立的样本图。添加以下内容。

在这里，你定义了一个方法 depthFirstSearch(from:)，它接收一个起始顶点，并按照访问的顺序返回一个顶点的列表。它使用了三个数据结构。

1. stack用来存储你在图中的路径。

2. pushed记住哪些顶点在之前被推送过，这样你就不会访问同一个顶点两次。它是一个Set，以确保快速的O(1)查找。

3. visited是一个数组，存储顶点被访问的顺序。为了启动该算法，你将源顶点添加到所有三个顶点中。

接下来，通过将注释替换为：完成该方法。

以下是发生的情况。

1. 你继续检查堆栈顶部的顶点，直到堆栈为空。

你给这个循环贴上了外层标签，这样你就有办法继续到下一个顶点，甚至在嵌套循环中也是如此。

2. 你找到当前顶点的所有邻接边。

3. 如果没有边，你就把顶点从堆栈中弹出，继续到下一个顶点。

4. 在这里，你循环浏览与当前顶点相连的每一条边，并检查是否已经看到了邻近的顶点。如果没有，你就把它推到堆栈上，并把它加入到访问过的数组中。把这个顶点标记为被访问的顶点似乎有点为时过早（你还没有偷看过它），但是，由于顶点是按照被添加到堆栈的顺序被访问的，所以它的结果是正确的。

5. 现在你已经找到了一个要访问的邻居，你继续进行外循环并移动到新推的邻居。

6. 如果当前顶点没有任何未访问的邻居，你知道你已经到达了一个死胡同，可以把它从堆栈中弹出。

一旦堆栈是空的，DFS算法就完成了！你所要做的就是把堆栈的数据返回给你。你所要做的就是按照你访问过的顶点的顺序返回这些顶点。

为了尝试你的代码，请在操场上添加以下内容。

let vertices = graph.depthFirstSearch(from: a) 
vertices.forEach { vertex in 
  print(vertex) 
}

请注意，使用DFS的访问节点的顺序。

0: A 
1: B 
4: E 
5: F 
6: G 
2: C 
7: H 
3: D

性能

DFS将至少访问每个顶点一次。这个过程的时间复杂度为O(V)。

在DFS中遍历一个图形时，你必须检查所有相邻的顶点以找到一个可以访问的顶点。这方面的时间复杂度为O(E)，因为在最坏的情况下，你必须访问图中的每一条边。

总之，深度优先搜索的时间复杂度是O(V+E)。

深度优先搜索的空间复杂度是O(V)，因为你必须在三个独立的数据结构中存储顶点：堆栈、推送和访问。

关键点

• 深度优先搜索（DFS）是另一种遍历或搜索图的算法。

• DFS尽可能地探索一个分支，直到它到达终点。

• 利用一个堆栈数据结构来跟踪你在图中的深度。

只有当你到达死胡同时才会弹出堆栈。

---

上一章	目录	下一章