36.图表¶

社交网络和世界各地的廉价机票预订有什么共同之处？你可以把这两个现实世界的模型都表示为graphs!

图是一种捕捉对象之间关系的数据结构。它是由vertices连接的edges组成的。

下图中的圆圈代表顶点，而边是连接它们的线。

加权图¶

在一个weighted graph中，每条边都有一个与之相关的权重，代表使用这条边的成本。这些权重让你选择两个顶点之间最便宜或最短的路径。

以航空业为例，想想一个具有不同飞行路径的网络：

在这个例子中，顶点代表一个州或国家，而边代表从一个地方到另一个地方的路线。与每条边相关的权重代表这两点之间的机票价格。使用这个网络，你可以为所有那些有预算观念的数字游牧民族确定从旧金山到新加坡的最便宜的航班!

定向图¶

除了给边分配权重外，你的图也可以有direction。有向图对遍历的限制更多，因为一条边只允许在一个方向上遍历。下图表示一个有向图。

你可以从这张图中看出很多东西：

有一个从香港到东京的航班。
没有从旧金山到东京的直达航班。
你可以买一张新加坡和东京之间的往返机票。
没有办法从东京到旧金山。

无向图¶

你可以把无向图看成是一个所有边都是双向的有向图。

在一个无向图中：

两个相连的顶点有来回走动的边。
一条边的权重适用于两个方向。

常见的操作¶

让我们建立一个图形的协议。

打开本章的启动项目。创建一个名为Graph.swift的新文件，并在该文件中加入以下内容：

public enum EdgeType {

  case directed
  case undirected
}

public protocol Graph {

  associatedtype Element

  func createVertex(data: Element) -> Vertex<Element>
  func addDirectedEdge(from source: Vertex<Element>,
                       to destination: Vertex<Element>,
                       weight: Double?)
  func addUndirectedEdge(between source: Vertex<Element>,
                         and destination: Vertex<Element>,
                         weight: Double?)
  func add(_ edge: EdgeType, from source: Vertex<Element>,
                             to destination: Vertex<Element>,
                             weight: Double?)
  func edges(from source: Vertex<Element>) -> [Edge<Element>]
  func weight(from source: Vertex<Element>,
              to destination: Vertex<Element>) -> Double?
}

该协议描述了图形的常见操作：

createVertex(data:)：创建一个顶点并将其添加到图中。
addDirectedEdge(from:to:weight:)：在两个顶点之间添加一条定向边。
addUndirectedEdge(between:and:weight:)：在两个顶点之间添加一条无向（或双向）边。
add(from:to:)：使用EdgeType在两个顶点之间添加一条有向或无向的边。
edges(from:)：返回一个来自特定顶点的出站边的列表。
weight(from:to:)：返回两个顶点之间的边缘的权重。

在下面的章节中，你将以两种方式实现这个协议：

使用邻接列表。
使用邻接矩阵。

在这之前，你必须首先建立类型来表示顶点和边。

定义一个顶点¶

创建一个名为Vertex.swift的新文件，并在该文件中添加以下内容：

public struct Vertex<T> {

  public let index: Int
  public let data: T
}

在这里，你已经定义了一个通用的Vertex结构。一个顶点在其图中有一个唯一的索引，并持有一段数据。

你将使用Vertex作为字典的关键类型，所以你需要符合Hashable。添加以下扩展来实现Hashable的要求：

extension Vertex: Hashable where T: Hashable {}
extension Vertex: Equatable where T: Equatable {}

Hashable协议继承于Equatable，所以你也必须满足这个协议的要求。编译器可以合成对两个协议的一致性，这就是为什么上面的扩展是空的。

最后，你想为Vertex提供一个自定义的字符串表示。紧接着添加以下内容：

extension Vertex: CustomStringConvertible {

  public var description: String {
    "\(index): \(data)"
  }
}

定义边¶

要连接两个顶点，它们之间必须有一条边!

创建一个名为Edge.swift的新文件，并在该文件中添加以下内容：

public struct Edge<T> {

  public let source: Vertex<T>
  public let destination: Vertex<T>
  public let weight: Double?
}

一个Edge连接两个顶点，并有一个可选的权重。很简单，不是吗？

邻接列表¶

你将学习的第一个图形实现使用一个adjacency list。对于图中的每一个顶点，图中存储了一个出站边的列表。

以下面这个网络为例：

下面的邻接列表描述了上面描述的航班网络：

从这个邻接列表中你可以学到很多东西：

新加坡的顶点有两条出去的边。有一个从新加坡到东京和香港的航班。
底特律有最小的出站流量。
东京是最繁忙的机场，有最多的出港航班。

在下一节中，你将通过存储一个dictionary of arrays来创建一个邻接列表。字典中的每个键都是一个顶点，在每个顶点中，字典中都有一个相应的边的数组。

实施¶

创建一个名为AdjacencyList.swift的新文件并添加以下内容：

public class AdjacencyList<T: Hashable>: Graph {

  private var adjacencies: [Vertex<T>: [Edge<T>]] = [:]

  public init() {}

  // more to come ...
}

在这里，你定义了一个AdjacencyList，它使用一个字典来存储边。注意，通用参数T必须是Hashable，因为它被用作字典中的一个键。

你已经采用了Graph协议，但仍然需要实现其要求。这就是你在下面几节中要做的事情。

创建一个顶点¶

给AdjacencyList添加以下方法：

public func createVertex(data: T) -> Vertex<T> {
  let vertex = Vertex(index: adjacencies.count, data: data)
  adjacencies[vertex] = []
  return vertex
}

在这里，你创建了一个新的顶点并将其返回。在邻接列表中，你为这个新顶点存储一个空的边数组。

创建一个有向边¶

回顾一下，有directed和undirected图。

从实现addDirectedEdge要求开始。添加以下方法：

public func addDirectedEdge(from source: Vertex<T>,
                            to destination: Vertex<T>,
                            weight: Double?) {
  let edge = Edge(source: source,
                  destination: destination,
                  weight: weight)
  adjacencies[source]?.append(edge)
}

该方法创建一条新的边并将其存储在邻接列表中。

创建一条无方向的边¶

你刚刚创建了一个方法来在两个顶点之间添加一条有向边。你将如何在两个顶点之间创建一条无方向的边？

记住，无定向图可以被看作是一个双向图。无向图中的每条边都可以被双向遍历。这就是为什么你要在addDirectedEdge之上实现addUndirectedEdge。因为这个实现是可重复使用的，你将把它作为一个协议扩展添加到Graph上。

在Graph.swift中，添加以下扩展：

extension Graph {

  public func addUndirectedEdge(between source: Vertex<Element>,
                                and destination: Vertex<Element>,
                                weight: Double?) {
    addDirectedEdge(from: source, to: destination, weight: weight)
    addDirectedEdge(from: destination, to: source, weight: weight)
  }
}

添加一条无方向的边和添加两条有方向的边是一样的。

现在你已经实现了addDirectedEdge和addUndirectedEdge，你可以通过委托给这些方法之一实现add。在同一个协议扩展中，添加：

public func add(_ edge: EdgeType, from source: Vertex<Element>,
                                  to destination: Vertex<Element>,
                                  weight: Double?) {
  switch edge {
  case .directed:
    addDirectedEdge(from: source, to: destination, weight: weight)
  case .undirected:
    addUndirectedEdge(between: source, and: destination, weight: weight)
  }
}

add方法是一个方便的辅助方法，可以创建有向或无向的边。这就是协议可以变得非常强大的地方!

任何采用Graph协议的人只需要实现addDirectedEdge就可以免费得到addUndirectedEdge和add!

检索一个顶点的传出边线¶

回到AdjacencyList.swift中，继续进行符合Graph的工作，添加以下方法：

public func edges(from source: Vertex<T>) -> [Edge<T>] {
  adjacencies[source] ?? []
}

这段代码是一个简单明了的实现。你要么返回存储的边，要么在source顶点未知时返回一个空数组。

检索一个边的重量¶

从新加坡到东京的航班是多少钱？

Add the following right after edges(from:):

public func weight(from source: Vertex<T>,
                   to destination: Vertex<T>) -> Double? {
  edges(from: source)
     .first { $0.destination == destination }?
     .weight
}

这里，你要找到从source到destination的第一条边；如果有的话，你要返回它的权重。

将邻接列表可视化¶

给AdjacencyList添加以下扩展，这样你就可以打印出你的图形的漂亮描述：

extension AdjacencyList: CustomStringConvertible {

  public var description: String {
    var result = ""
    for (vertex, edges) in adjacencies { // 1
      var edgeString = ""
      for (index, edge) in edges.enumerated() { // 2
        if index != edges.count - 1 {
          edgeString.append("\(edge.destination), ")
        } else {
          edgeString.append("\(edge.destination)")
        }
      }
      result.append("\(vertex) ---> [ \(edgeString) ]\n") // 3
    }
    return result
  }
}

下面是上面代码中的情况：

循环浏览adjacencies中的每个键值对。
对于每个顶点，你循环浏览它的所有出站边，并在输出中添加一个适当的字符串。
最后，对于每个顶点，你都要打印顶点本身和它的出站边。

你终于完成了你的第一个图! 现在让我们通过建立一个网络来试试吧。

建立一个网络¶

让我们回到航班的例子，构建一个以价格为权重的航班网络。

在主playground页面内，添加以下代码：

let graph = AdjacencyList<String>()

let singapore = graph.createVertex(data: "Singapore")
let tokyo = graph.createVertex(data: "Tokyo")
let hongKong = graph.createVertex(data: "Hong Kong")
let detroit = graph.createVertex(data: "Detroit")
let sanFrancisco = graph.createVertex(data: "San Francisco")
let washingtonDC = graph.createVertex(data: "Washington DC")
let austinTexas = graph.createVertex(data: "Austin Texas")
let seattle = graph.createVertex(data: "Seattle")

graph.add(.undirected, from: singapore, to: hongKong, weight: 300)
graph.add(.undirected, from: singapore, to: tokyo, weight: 500)
graph.add(.undirected, from: hongKong, to: tokyo, weight: 250)
graph.add(.undirected, from: tokyo, to: detroit, weight: 450)
graph.add(.undirected, from: tokyo, to: washingtonDC, weight: 300)
graph.add(.undirected, from: hongKong, to: sanFrancisco, weight: 600)
graph.add(.undirected, from: detroit, to: austinTexas, weight: 50)
graph.add(.undirected, from: austinTexas, to: washingtonDC, weight: 292)
graph.add(.undirected, from: sanFrancisco, to: washingtonDC, weight: 337)
graph.add(.undirected, from: washingtonDC, to: seattle, weight: 277)
graph.add(.undirected, from: sanFrancisco, to: seattle, weight: 218)
graph.add(.undirected, from: austinTexas, to: sanFrancisco, weight: 297)

print(graph)

你应该在你的playground上得到以下输出：

2: Hong Kong ---> [ 0: Singapore, 1: Tokyo, 4: San Francisco ]
4: San Francisco ---> [ 2: Hong Kong, 5: Washington DC, 7: Seattle, 6: Austin Texas ]
5: Washington DC ---> [ 1: Tokyo, 6: Austin Texas, 4: San Francisco, 7: Seattle ]
6: Austin Texas ---> [ 3: Detroit, 5: Washington DC, 4: San Francisco ]
7: Seattle ---> [ 5: Washington DC, 4: San Francisco ]
0: Singapore ---> [ 2: Hong Kong, 1: Tokyo ]
1: Tokyo ---> [ 0: Singapore, 2: Hong Kong, 3: Detroit, 5: Washington DC ]
3: Detroit ---> [ 1: Tokyo, 6: Austin Texas ]

这个输出显示了一个邻接列表的视觉描述。你可以看到所有来自任何地方的出港航班! 很酷，是吧？

你还可以获得其他有用的信息，如：

从新加坡到东京的航班是多少钱？

graph.weight(from: singapore, to: tokyo)

从旧金山飞出的航班都有哪些？

print("San Francisco Outgoing Flights:")
print("--------------------------------")
for edge in graph.edges(from: sanFrancisco) {
  print("from: \(edge.source) to: \(edge.destination)")
}

你刚刚用邻接列表创建了一个图，其中你用一个字典来存储每个顶点的传出边。让我们来看看如何存储顶点和边的另一种方法。

毗连矩阵¶

一个adjacency matrix使用一个方形矩阵来表示一个图。这个矩阵是一个二维数组，其中matrix[row][column]的值是row和column的顶点之间的边缘的权重。

下面是一个有向图的例子，描述了一个前往不同地方的飞行网络。权重代表机票的成本。

下面的邻接矩阵描述了上面描述的航班网络。

不存在的边的权重为0。

与邻接列表相比，这个矩阵有点难读。使用左边的顶点阵列，你可以从矩阵中了解到很多东西。比如说：

[0][1]是300，所以有一个从新加坡到香港的航班，价格是300美元。
[2][1]是0，所以没有从东京到香港的航班。
[1][2]是250，所以有一个从香港到东京的航班，价格是250美元。
[2][2]是0，所以没有从东京到东京的航班!

Note

在矩阵的中间有一条粉红色的线。当行和列相等时，这代表一个顶点和它自己之间的一条边，这是不允许的。

实施¶

创建一个名为AdjacencyMatrix.swift的新文件，并在其中添加以下内容：

public class AdjacencyMatrix<T>: Graph {

  private var vertices: [Vertex<T>] = []
  private var weights: [[Double?]] = []

  public init() {}

  // more to come ...
}

在这里，你定义了一个AdjacencyMatrix，它包含一个顶点数组和一个相邻矩阵，用来跟踪边和它们的权重。

就像以前一样，你已经声明了与Graph的一致性，但仍然需要实现这些要求。

创建一个顶点¶

给AdjacencyMatrix添加以下方法：

public func createVertex(data: T) -> Vertex<T> {
  let vertex = Vertex(index: vertices.count, data: data)
  vertices.append(vertex) // 1
  for i in 0..<weights.count { // 2
    weights[i].append(nil)
  }
  let row = [Double?](repeating: nil, count: vertices.count) // 3
  weights.append(row)
  return vertex
}

要在一个邻接矩阵中创建一个顶点，你要做的是：

在阵列中添加一个新的顶点。
在矩阵的每一行添加一个nil权重，因为当前的顶点都没有与新顶点相连的边。

在矩阵中添加一个新的行。这一行保存了新顶点的出站边。

创建边缘¶

创建边缘就像填入矩阵一样简单。添加以下方法：

public func addDirectedEdge(from source: Vertex<T>,
                            to destination: Vertex<T>, weight: Double?) {
  weights[source.index][destination.index] = weight
}

请记住，addUndirectedEdge和add在协议扩展中有一个默认的实现，所以这就是你需要做的所有事情!

检索一个顶点的出场边线¶

添加以下方法：

public func edges(from source: Vertex<T>) -> [Edge<T>] {
  var edges: [Edge<T>] = []
  for column in 0..<weights.count {
    if let weight = weights[source.index][column] {
      edges.append(Edge(source: source,
                        destination: vertices[column],
                        weight: weight))
    }
  }
  return edges
}

要检索一个顶点的外向边，需要在矩阵中搜索这个顶点的行，寻找非nil的权重。

每个非nil的权重都对应着一条出站边。目标是与发现权重的那一列相对应的顶点。

检索一条边的权重¶

获取一条边的权重非常简单，只要在邻接矩阵中查找该值即可。添加这个方法：

public func weight(from source: Vertex<T>,
                   to destination: Vertex<T>) -> Double? {
  weights[source.index][destination.index]
}

可视化一个邻接矩阵¶

最后，添加以下扩展，这样你就可以打印出一个漂亮的、可读的图的描述：

extension AdjacencyMatrix: CustomStringConvertible {

  public var description: String {
    // 1
    let verticesDescription = vertices.map { "\($0)" }
                                      .joined(separator: "\n")
    // 2
    var grid: [String] = []
    for i in 0..<weights.count {
      var row = ""
      for j in 0..<weights.count {
        if let value = weights[i][j] {
          row += "\(value)\t"
        } else {
          row += "ø\t\t"
        }
      }
      grid.append(row)
    }
    let edgesDescription = grid.joined(separator: "\n")
    // 3
    return "\(verticesDescription)\n\n\(edgesDescription)"
  }
}

以下是有关步骤：

你首先创建一个顶点的列表。
然后，你逐行建立一个权重网格。
最后，你把这两个描述连在一起，并返回它们。

建立一个网络¶

你将重复使用AdjacencyList中的同一个例子：

进入Playground主页面并替换：

let graph = AdjacencyList<String>()

为：

let graph = AdjacencyMatrix<String>()

AdjacencyMatrix和AdjacencyList符合相同的协议Graph，所以代码的其余部分保持不变。

你应该在你的Playground上得到以下输出：

0: Singapore
1: Tokyo
2: Hong Kong
3: Detroit
4: San Francisco
5: Washington DC
6: Austin Texas
7: Seattle
ø   500.0 300.0 ø   ø   ø   ø   ø   
500.0 ø   250.0 450.0 ø   300.0 ø   ø   
300.0 250.0 ø   ø   600.0 ø   ø   ø   
ø   450.0 ø   ø   ø   ø   50.0  ø   
ø   ø   600.0 ø   ø   337.0 297.0 218.0
ø   300.0 ø   ø   337.0 ø   292.0 277.0
ø   ø   ø   50.0  297.0 292.0 ø   ø   
ø   ø   ø   ø   218.0 277.0 ø   ø   
San Francisco Outgoing Flights:
--------------------------------
from: 4: San Francisco to: 2: Hong Kong
from: 4: San Francisco to: 5: Washington DC
from: 4: San Francisco to: 6: Austin Texas
from: 4: San Francisco to: 7: Seattle

就视觉上的美感而言，邻接列表比邻接矩阵更容易被关注和追踪。让我们分析一下这两种方法的共同操作，看看它们的表现如何。

图形分析¶

这个图表总结了用邻接列表与邻接矩阵表示的图的不同操作的成本。

V代表顶点，E代表边。

邻接列表比邻接矩阵占用更少的存储空间。一个邻接列表只需存储所需的顶点和边的数量。至于邻接矩阵，请记住，行和列的数量等于顶点的数量。这解释了O(V²)的二次空间复杂性。

在邻接列表中，增加一个顶点是很有效的。只需创建一个顶点并在字典中设置其键值对。它被摊销为O(1)。当向邻接矩阵添加顶点时，你必须在每一行添加一列，并为新顶点创建一个新行。这至少是O(V)，如果你选择用一个连续的内存块来表示你的矩阵，这可能是O(V²)。

在这两种数据结构中，增加一条边都是有效的，因为它们都是恒定时间。邻接列表会追加到出站边缘的数组中。邻接矩阵只是简单地设置二维数组中的值。

当试图找到一个特定的边或权重时，邻接列表就会失去作用。要在邻接列表中找到一条边，你必须获得出站边的列表，并在每条边上循环，找到一个匹配的目的地。这发生在O(V)时间内。对于邻接矩阵，寻找一条边或权重是以恒定的时间访问，从二维数组中检索出数值。

你应该选择哪种数据结构来构建你的图？

如果你的图中有很少的边，它被认为是一个sparse图，邻接列表将是一个很好的选择。对于稀疏图来说，邻接矩阵是一个糟糕的选择，因为没有很多边，所以会浪费大量的内存。

如果你的图有很多边，它被认为是一个dense graph，邻接矩阵将是一个更好的选择，因为你能更快地访问你的权重和边。

关键点¶

你可以通过vertices和edges来表示现实世界的关系。
将vertices视为对象，将edges视为对象之间的关系。
加权图的每条边都有一个权重。
有向图的边在一个方向上移动。
无向图的边是双向指向的。
邻接列表为每个顶点存储了一个外向边的列表。
邻接矩阵使用一个方形矩阵来表示一个图。
当你的图有最少的边时，邻接列表通常适用于sparse graphs。
当你的图有很多边时，邻接矩阵通常适用于dense graphs。