39.广度优先搜索的挑战¶

挑战1：最大队列规模¶

对于下面这个无向图，请列出队列中的maximum项目数。假设起始顶点是A。

挑战2：迭代式`BFS`¶

在这一章中，你讨论了广度优先搜索的迭代实现。现在写一个递归实现。

挑战3：断开连接的图形¶

给Graph添加一个方法，以检测图是否断开连接。下面是一个断开连接的图的例子：

为了帮助你解决这个难题，在Graph协议中增加了一个属性allVertices：

var allVertices: [Vertex<Element>] { get }

这个属性已经由AdjacencyMatrix和AdjacencyList实现了。

解决方案¶

挑战1的解决方案¶

队列中的最大项目数是3。

挑战2的解决方案¶

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

extension Graph where Element: Hashable  {

  func bfs(from source: Vertex<Element>) -> [Vertex<Element>] {
    var queue = QueueStack<Vertex<Element>>() // 1
    var enqueued: Set<Vertex<Element>> = [] // 2
    var visited: [Vertex<Element>] = [] // 3

    // 4
    queue.enqueue(source)
    enqueued.insert(source)
    // 5
    bfs(queue: &queue, enqueued: &enqueued, visited: &visited)
    // 6
    return visited
  }
}

bfs接受source顶点以开始穿越：

queue跟踪接下来要访问的邻近顶点。
enqueued记住哪些顶点已经被添加到队列中。你可以使用Set进行O(1)查询。一个数组是O(n)。
visited是一个数组，存储顶点被探索的顺序。
通过插入source顶点来启动算法。
通过调用一个辅助函数在图上递归地执行bfs。
按顺序返回所访问的顶点。

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

private func bfs(queue: inout QueueStack<Vertex<Element>>,
                 enqueued: inout Set<Vertex<Element>>,
                 visited: inout [Vertex<Element>]) {
  guard let vertex = queue.dequeue() else { // 1
    return
  }
  visited.append(vertex) // 2
  let neighborEdges = edges(from: vertex) // 3
  neighborEdges.forEach { edge in
    if !enqueued.contains(edge.destination) { // 4
      queue.enqueue(edge.destination)
      enqueued.insert(edge.destination)
    }
  }
  // 5
  bfs(queue: &queue, enqueued: &enqueued, visited: &visited)
}

Base case，递归地继续从队列中提取一个顶点，直到它为空。
将顶点标记为已访问。
对于来自当前vertex的每一条邻接边。
在插入队列之前，检查相邻顶点是否已被访问。
递归地执行bfs，直到队列为空。

广度优先搜索的总体时间复杂度为O(V+E)。

挑战3的解决方案¶

如果两个节点之间不存在路径，则称该图为断开连接。

extension Graph where Element: Hashable {

  func isDisconnected() -> Bool {
    guard let firstVertex = allVertices.first else { // 1
      return false
    }
    let visited = breadthFirstSearch(from: firstVertex) // 2
    for vertex in allVertices { // 3
      if !visited.contains(vertex) {
        return true
      }
    }
    return false
  }
}

如果没有顶点，将该图视为连接图。
从第一个顶点开始进行广度优先搜索。这个过程将返回所有被访问的节点。
遍历图中的每一个顶点，检查它是否曾经被访问过。

如果在visited集合中缺少一个顶点，那么该图就是断开的。