图（Graphs）
2020-08-07 本文已影响0人
Bel李玉
图是用来体现对象之间联系的一种数据结构，它由顶点(vertices)和 边(edges)
例如下面的图所示，顶点由圆圈表示，边由连接两个顶点的直线表示。
Graph1.png
有权图
在有权图中，每一条边都有一个权重。
在航空业，设想一下以下飞行路线：
Graph2.png
在这个示例中，图的顶点代表一个国家或者一个城市，边代表从一个地方到另一个地方的路径，每一条边的权重代表该航线所需要的花费。
通过该网络，你可以从中找到从 San Francisco 到 Singapore最小花费的路线图。
有向图
有向图对遍历的限制更大，因为一条边可能只允许在一个方向上遍历。
Graph3.png
我们可以从上图得到很多信息：
- 从 HongKong 到 东京 有一个航班。
- 从 San Francisco 到 Tokyo 没有直达航班。
- 从 Singapore 到 Tokyo是有票的。
- 从 Tokyo 到 San Francisco 是没有航线的。
无向图
你可以将一个无向图看作是一个每一条边都是双向的图。
在无向图中：
- 在两个顶点中，有两个边。
-
在来回两个边中，有一样的权重。
Graph4.png
共同的接口
我们来定义图数据结构该遵守的协议
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:):返回两个顶点的权重值。
在接下来的部分，可以通过两种方式实现该协议： - 使用邻接表。
- 使用邻接矩阵。
定义顶点
Graph5.png
顶点(Vertex)的定义如下：
public struct Vertex<T> {
public let index: Int
public let data: T
}
每个顶点都有一个唯一的 index，并且有一个data 值。接下来，我们会将 Vertex作为 字典的 key，所以 Vertex需要遵守 Hashable协议
extension Vertex: Hashable{
// 以 index 的哈希值作为唯一性标识
public var hashValue: Int {
return index.hashValue
}
public static func ==(lhs: Vertex, rhs: Vertex) -> Bool {
return lhs.index == rhs.index
}
}
最后，我们需要提供一个自定义的字符串表达：
extension Vertex: CustomStringConvertible {
public var description: String {
return "\(index): \(data)"
}
}
定义边（Edge）
为了连接两个顶点，在两个顶点需要有一条边。
public struct Edge<T> {
public let source: Vertex<T>
public let destination: Vertex<T>
public let weight: Double?
}
一个边对象的权重是可选的。
邻接表(Adjacency list)
首先我们用 邻接表 来实现表。
我们以如下图结构为例：
Graph6.png
使用邻接表表示以上航班信息如下所示：
Graph7.png
1，Signapore有两个直达航班，分别到 Tokyo 和 HongKong。
2，Detroit 的直达航班最少。
3，Tokyo 是最忙的机场，有最多的直达航班。
接下来，我们将使用数组类型的字典来实现邻接表，将 vertex作为字典的 key ,将相关联的边(edge)作为 value。
实现
public class AdjacencyList<T: Hashable>: Graph {
private var adjacencies: [Vertex<T>: [Edge<T>]] = [:]
public init() {}
// more to come ...
}
我们使用字典存储所有的边，泛型T需要遵守 Hashable，因为我们要将它作为字典的key。接下来，我们要一一实现协议方法。
构造边
public func createVertex(data: T) -> Vertex<T> {
let vertex = Vertex(index: adjacencies.count, data: data)
adjacencies[vertex] = []
return vertex
}
构造单向边
我们前面说过，图分为有向图和无向图
Graph8.png
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)
}
该方法创建了一个新边并且将它存储到邻接表中。
构造无向边（双向边）
无向边实际上就是一个双向边，我们可以重复利用创建单向边的方法，在两个顶点之间创建两个边。
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)
}
}
添加一个无向边和添加两个单向边一样。
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)
}
}
获取顶点所有的边
我们在实现中添加如下实现：
public func edges(from source: Vertex<T>) -> [Edge<T>] {
return adjacencies[source] ?? []
}
这是edges最直接的实现，如果 source 不可知，则返回空数组。
获取边的权重
从 Singapore 到 Tokyo 的航班要花费多少呢？
Graph9.png
在
edges(from:)方法中添加如下实现：
public func weight(from source: Vertex<T>,
to destination: Vertex<T>) -> Double? {
return edges(from: source)
.first { $0.destination == destination }?
.weight
}
先找到 source 的所有边，然后根据 destination ,找到该 边 ，返回该边的权重值。
将邻接表可视化
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
}
}
邻接矩阵
邻接矩阵使用二维数组去表示一个图，matrix[row][column] 表示row处顶点到column处顶点的权重。
下面的图表示直达各个城市的航班，权重标志该条航线所需要花费的费用
Graph10.png
如果边不存在，权重则为0
Graph11.png
和邻接表相比较，邻接矩阵有一点难懂。
- [0] [1]的值为300，表示从Singapore 到 HongKong 需要花费 $300。
- [2] [1]的值为 0，表示从Tokyo 到 HongKong没有航班。
- [1] [2]的值是 250，表示从HongKong到Tokyo需要花费 250。
- [2] [2]的值是0，表示没有航班从Tokyo 到Tokyo。
实现
public class AdjacencyMatrix<T>: Graph {
private var vertices: [Vertex<T>] = []
private var weights: [[Double?]] = []
public init() {}
// more to come ...
}
vertices用来保存所有的节点，weights用来保存顶点之间的权重。
创建顶点
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
}
1，向顶点数组中添加一个新顶点。
Graph12.png
1，向矩阵的添加新的一行，这一行表示到新顶点的边。
Graph13.png
创建边
创建边和填充该二维矩阵一样：
public func addDirectedEdge(from source: Vertex<T>,
to destination: Vertex<T>, weight: Double?) {
weights[source.index][destination.index] = weight
}
获取一个顶点的所有边
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，则创建一个顶点，并添加到 edges里面。
获取一条边的权重
public func weight(from source: Vertex<T>,
to destination: Vertex<T>) -> Double? {
return weights[source.index][destination.index]
}
最后附上本文的相关代码DataAndAlgorim
