第36章：图

社交网络与预订世界各地的廉价航班有什么共同之处？你可以把这两个现实世界的模型用图来表示!

图是一种捕捉对象之间关系的数据结构。它是由边邻接的顶点组成的。

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

加权图

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

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

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

有向图

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

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

无定向图

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

在一个无向图中。

一个无向图

常见操作

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

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


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

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

定义一个顶点

一个顶点的集合--还不是一个图

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

public struct Vertex<T> {
  public let index: Int 
  public let data: T
}

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

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

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

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

最后，你想提供一个顶点的自定义字符串表示。在后面添加以下内容。

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邻接两个顶点，并有一个可选的权重。很简单，不是吗？

毗连列表

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

以下面这个网络为例。

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

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

  1. 新加坡的顶点有两条出去的边。有一个从新加坡到东京和香港的航班。

  2. 底特律有最小的出站流量。

  3. 东京是最繁忙的机场，有最多的出港航班。

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

实现

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

public class AdjacencyList<T: Hashable>: Graph { 
  private var adjacencies: [Vertex<T>: [Edge<T>]] = [:] 
  public init() {} 
  // more to come ...
}

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

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

创建一个顶点

在 AdjacencyList 中添加以下方法。

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

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

创建一个有向边

回顾一下，图有有向和无向之分。

首先实现addDirectedEdge的要求。添加以下方法。


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

创建一条无方向的边

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

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

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

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

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


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

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

检索一个顶点的传出边线

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

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

这段代码是一个直接的实现。你要么返回存储的边，要么在源顶点未知时返回一个空数组。

检索一条边的权重

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


在edges(from:)后面添加以下内容。

在这里，你找到了从源点到目的地的第一条边；如果有的话，你返回它的权重。

邻接表的可视化

为AdjacencyList添加以下扩展，这样你就可以打印出一个漂亮的图的描述。

下面是上面代码中的内容。

  1. 循环浏览邻接关系中的每个键值对。

  2. 对于每个顶点，你循环浏览它所有的出站边，并在输出中添加一个适当的字符串。

  3. 最后，对于每个顶点，你都要打印顶点本身和它的出站边。你终于完成了你的第一个图! 现在让我们通过建立一个网络来试试吧。

构建一个网络

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

在主操场页面中，添加以下代码。


你应该在你的游乐场得到以下输出。

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

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

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

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

邻接矩阵

毗连矩阵使用一个正方形矩阵来表示一个图。这个矩阵是一个二维数组，矩阵[行][列]的值是行和列的顶点之间的边缘的权重。

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

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

不存在的边的权重为0。

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

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

实现

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

public class AdjacencyMatrix<T>: Graph { 
  private var vertices: [Vertex<T>] = [] 
  private var weights: [[Double?]] = [] 
  public init() {} 
  // more to come ...
}

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

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

创建一个顶点

在AdjacencyMatrix中添加以下方法。

要在一个邻接矩阵中创建一个顶点，你需要

  1. 在数组中添加一个新的顶点。

  2. 给矩阵中的每一行添加一个nil权重，因为当前的顶点都没有到新顶点的边。


3. 在矩阵中添加一个新的行。这一行存放新顶点的出站边。

创建边

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

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

从一个顶点检索出走的边

添加以下方法。


要检索一个顶点的出走边，需要在矩阵中搜索这个顶点的那一行，寻找不为零的权重。

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

检索一条边的权重

获取一条边的权重非常容易，只需在邻接矩阵中查找该值。添加这个方法。

可视化一个邻接矩阵

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


以下是有关步骤。

  1. 你首先创建一个顶点的列表。

  2. 然后，你逐行建立一个权重网格。

  3. 最后，你把这两个描述连在一起并返回。

建立一个网络

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

转到主操场页面并替换。

let graph = AdjacencyList<String>()

用:

let graph = AdjacencyMatrix<String>()

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

你应该在你的操场上得到以下输出。

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

图表分析

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


V代表顶点，E代表边。

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

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

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

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

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

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

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

关键点

上一章 目录 下一章