41.深度优先搜索的挑战¶

挑战1：`BFS`或`DFS`¶

对于以下两个例子，哪种遍历方法（深度优先或广度优先）更有利于发现两个节点之间是否存在路径？解释一下原因。

从A到F的路径。
从A到G的路径。

挑战2：递归`DFS`¶

在本章中，你讲了深度优先搜索的迭代实现。现在写一个递归实现。

挑战3：检测循环¶

给Graph添加一个方法，检测一个directed图是否有一个周期。

解决方案¶

挑战1的解决方案¶

从A到F的路径。使用深度优先，因为你要找的路径在图中比较深。
从A到G的路径。使用广度优先，因为你要找的路径在根附近。

挑战2的解决方案¶

在深度优先搜索一章中，你学到了如何迭代实现该算法的方法。让我们看看如何递归地实现它。

extension Graph where Element: Hashable {

  func depthFirstSearch(from start: Vertex<Element>)
                        -> [Vertex<Element>] {
    var visited: [Vertex<Element>] = [] // 1
    var pushed: Set<Vertex<Element>> = [] // 2
    depthFirstSearch(from: start, // 3
                     visited: &visited,
                     pushed: &pushed)
    return visited
  }
}

visited按顺序记录所访问的顶点。
pushed记录哪些顶点被访问过。
通过调用一个辅助函数递归地执行深度优先搜索。

这个辅助函数看起来像这样：

func depthFirstSearch(from source: Vertex<Element>,
                      visited: inout [Vertex<Element>],
                      pushed: inout Set<Vertex<Element>>) {
  pushed.insert(source) // 1
  visited.append(source)

  let neighbors = edges(from: source)
  for edge in neighbors { // 2
    if !pushed.contains(edge.destination) {
      depthFirstSearch(from: edge.destination, // 3
                       visited: &visited,
                       pushed: &pushed)
    }
  }
}

将source顶点插入队列，并将其标记为访问。
对于每条相邻的边。
只要相邻的顶点还没有被访问过，就继续递归地沿着分支深入下去。

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

挑战3的解决方案¶

当边和顶点的路径回到同一源头时，图就有一个循环。

extension Graph where Element: Hashable {

  func hasCycle(from source: Vertex<Element>) -> Bool  {
    var pushed: Set<Vertex<Element>> = [] // 1
    return hasCycle(from: source, pushed: &pushed) // 2
  }
}

pushed是用来记录所有被访问的顶点。
通过调用一个辅助函数，递归地检查图中是否有一个循环。