跳转至

40.深度优先搜索

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

DFS有很多的应用：

  • 拓扑结构的排序。
  • 检测一个周期。
  • 寻路，比如在迷宫游戏中。
  • 寻找稀疏图中的连接组件。

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

示例

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

img

你将使用一个stack来记录你所移动的关卡。堆栈的last-in-first-out方法有助于回溯。栈上的每一个push都意味着你向更深的层次移动。如果你走到了死胡同，你可以pop返回到前一关。

img

  1. 和上一章一样，你选择A作为起始顶点，并将其加入堆栈。
  2. 只要堆栈不是空的，你就访问堆栈上的顶点，并推送尚未访问的第一个邻近顶点。在这种情况下，你访问A并推送B。

Note

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

img

  1. 你访问了B并推了E，因为A已经被访问了。
  2. 你访问E并推送F。

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

img

  1. 你访问F并推动G。
  2. 你访问G并推C。

img

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

img

  1. F也没有剩余的未访问的邻居，所以弹出F。
  2. 现在，你回到了E处。它的邻居H仍然没有被访问，所以你把H推到栈上。

img

  1. 访问H的结果是另一个死胡同，所以弹出H。
  2. E也没有任何可用的邻居，所以弹出它。

img

  1. 对B来说也是如此，所以弹出B。
  2. 这使你回到了A，它的邻居D仍然需要被访问，所以你把D推到栈上。

img

  1. 访问D的结果是另一个死胡同，所以弹出D。
  2. 你回到A，但这次没有可用的邻居可以推送，所以你弹出A。堆栈现在是空的，DFS已经完成。

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

img

实施

打开本章的启动playground。这个playground包含一个图形的实现，以及一个堆栈，你将用它来实现DFS。

在你的主playground文件中，你会注意到一个预先建立的样本图。添加以下内容：

extension Graph where Element: Hashable {

  func depthFirstSearch(from source: Vertex<Element>)
      -> [Vertex<Element>] {
    var stack: Stack<Vertex<Element>> = []
    var pushed: Set<Vertex<Element>> = []
    var visited: [Vertex<Element>] = []

    stack.push(source)
    pushed.insert(source)
    visited.append(source)

    // more to come ...

    return visited
  }
}

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

  1. stack用于存储你在图中的路径。
  2. pushed记住哪些顶点以前被推过，这样你就不会访问同一个顶点两次。它是一个Set，以确保快速O(1)查找。
  3. visited是一个数组，存储顶点被访问的顺序。

为了开始这个算法，你把source顶点加入到所有三个顶点中。

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

outer: while let vertex = stack.peek() { // 1
  let neighbors = edges(from: vertex) // 2
  guard !neighbors.isEmpty else { // 3
    stack.pop()
    continue
  }
  for edge in neighbors { // 4
    if !pushed.contains(edge.destination) {
      stack.push(edge.destination)
      pushed.insert(edge.destination)
      visited.append(edge.destination)
      continue outer // 5
    }
  }
  stack.pop() // 6
}

以下是发生的情况：

  1. 你继续检查堆栈顶部的顶点，直到堆栈为空。你把这个循环标记为outer，这样你就有办法继续到下一个顶点，即使是在嵌套循环中。
  2. 你找到当前顶点的所有邻接边。
  3. 如果没有边，你就从堆栈中弹出顶点并继续下一个顶点。
  4. 在这里，你循环浏览与当前顶点相连的每一条边，并检查是否已经看到了邻近的顶点。如果没有，你就把它推到堆栈中，并把它加入到visited数组中。把这个顶点标记为被访问的顶点似乎有点为时过早（你还没有偷看过它），但是，由于顶点是按照被添加到堆栈的顺序被访问的，所以它的结果是正确的。
  5. 现在你已经找到了一个要访问的邻居，你继续进行outer循环并移动到新推的邻居。
  6. 如果当前顶点没有任何未访问的邻居，你知道你已经到达了一个死胡同，可以把它从堆栈中弹出。

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

为了尝试你的代码，请在playground上添加以下内容：

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)，因为你必须在三个独立的数据结构中存储顶点：stack、pushed和visited。

关键点

  • 深度优先搜索（DFS）是另一种遍历或搜索图的算法。
  • DFS尽可能地探索一个分支，直到它到达终点。
  • 利用一个堆栈数据结构来跟踪你在图中的深度。只有当你到达死胡同时才会弹出堆栈。