37.图形挑战¶

挑战1：计算路径的数量¶

写一个方法来计算有向图中两个顶点之间的路径数。下面的示例图有五条从A到E的路径。

挑战2：用图表示你的朋友¶

文森特有三个朋友：切斯利、鲁伊斯和帕特里克。鲁伊兹也有朋友。雷，孙，以及文森特的一个共同朋友。帕特里克是科尔和凯里的朋友。Cole是Ruiz和Vincent的朋友。建立一个代表这个友谊图的邻接列表。鲁伊兹和文森特有哪些共同的朋友？

解决方案¶

挑战1的解决方案¶

我们的目标是写一个函数，找出图中两个顶点之间的路径数。一种解决方案是进行深度优先的遍历，并跟踪所访问的顶点。

extension Graph where Element: Hashable {
  public func numberOfPaths(from source: Vertex<Element>,
                            to destination: Vertex<Element>) -> Int {
    var numberOfPaths = 0 // 1
    var visited: Set<Vertex<Element>> = [] // 2
    paths(from: source,
          to: destination,
          visited: &visited,
          pathCount: &numberOfPaths) // 3
    return numberOfPaths
  }

}

在这里，你要做以下工作：

numberOfPath记录在source和destination之间找到的路径数量。
visited是一个Set，记录了所有被访问的顶点。
paths是一个递归辅助函数，接收四个参数。前两个参数是source和destination顶点。最后两个参数，visited跟踪所访问的顶点，numberOfPaths跟踪发现的路径数量。后面两个参数是在paths中修改的。

在numberOfPaths函数后面添加以下内容：

func paths(from source: Vertex<Element>,
           to destination: Vertex<Element>,
           visited: inout Set<Vertex<Element>>,
           pathCount: inout Int) {
  visited.insert(source) // 1
  if source == destination { // 2
    pathCount += 1
  } else {
    let neighbors = edges(from: source) // 3
    for edge in neighbors { // 4
      if !visited.contains(edge.destination) {
        paths(from: edge.destination,
              to: destination,
              visited: &visited,
              pathCount: &pathCount)
      }
    }
  }
  // 5
  visited.remove(source)
}

要获得从source到destination的路径：

将source的顶点标记为已访问，从而启动该算法。
检查source是否是 destination。如果是，你就找到了一条路径，将计数增加1。
如果不是，则获取所有与source顶点相邻的边。
对于每一条边，如果它以前没有被访问过，就递归地遍历邻近的顶点，以找到一条通往目的地顶点的路径。
将source顶点从访问集中删除，这样你就可以继续找到通往该节点的其他路径。

你正在做一个深度优先的图形遍历。你递归地潜入一条路径，直到到达目的地，然后通过弹出堆栈来回溯。时间复杂度为O(V + E)。

挑战2的解决方案¶

这个解决方案使用你在上一章建立的AdjacencyList API。你可以使用任何非零的权重，但一个好的默认值是1。

let graph = AdjacencyList<String>()

let vincent = graph.createVertex(data: "vincent")
let chesley = graph.createVertex(data: "chesley")
let ruiz = graph.createVertex(data: "ruiz")
let patrick = graph.createVertex(data: "patrick")
let ray = graph.createVertex(data: "ray")
let sun = graph.createVertex(data: "sun")
let cole = graph.createVertex(data: "cole")
let kerry = graph.createVertex(data: "kerry")

graph.add(.undirected, from: vincent, to: chesley, weight: 1)
graph.add(.undirected, from: vincent, to: ruiz, weight: 1)
graph.add(.undirected, from: vincent, to: patrick, weight: 1)
graph.add(.undirected, from: ruiz, to: ray, weight: 1)
graph.add(.undirected, from: ruiz, to: sun, weight: 1)
graph.add(.undirected, from: patrick, to: cole, weight: 1)
graph.add(.undirected, from: patrick, to: kerry, weight: 1)
graph.add(.undirected, from: cole, to: ruiz, weight: 1)
graph.add(.undirected, from: cole, to: vincent, weight: 1)
print(graph)

你可以简单地看一下图表，找到共同的朋友。

print("Ruiz and Vincent both share a friend name Cole")

如果你想用程序来解决这个问题，你可以利用元素是Hashable的事实，找到Ruiz和Vincent的朋友的Set的交点。

let vincentsFriends = Set(graph.edges(from: vincent).map { $0.destination.data })
let mutual = vincentsFriends.intersection(graph.edges(from: ruiz).map { $0.destination.data })
print(mutual)