Graph(图)-Swift实现

定义及特性

• 图代表一组事物及事物之间的关系，所以图由事物和关系组成，即由顶点(vertices)和边(edge)组成；

  
  图.png
• 树形结构和链表都可以说是一种特殊的图类型结构；
• 图根据链接顶点的边是否有方向，分为有向图和无向图；

• 同时在链接定点的边上可以赋值，称为权重，权重根据图的实际情况，代表不同意义下的一些值或者开销，根据权重会进行一些计算；
  下图就是一个边带有权重的有向图

  
  有向图.png

图的实现

图的实现有很多种方式，常用的有两种方法：邻接表和邻接矩阵，下面我们用邻接表的方式来表示图。
用链接表表示图，简单一点的实现是，数组-字典模式，即将图的所有顶点作为键名，将与对应顶点相连的邻居存储在数组中，作为字典的键值。我们的实现思路相差不多，不过功能更多一点

• 定义顶点

//1
struct Vertex<T: Hashable> {
    var data: T
}

//2
extension Vertex: Hashable {
    var hashValue: Int {
        return data.hashValue
    }
    
    static func == (lhs: Vertex<T>, rhs: Vertex<T>) -> Bool {
        return lhs.data == rhs.data
    }
}
//3
extension Vertex: CustomStringConvertible {
    var description: String {
        return "\(data)"
    }
}

1.我们定义顶点，结构体Vertex，这个结构体内部含有一个泛型的data变量，因为我们要将顶点作为键名存储在字典中，所以我们要求这个泛型需要遵守Hashable协议；
2.遵守Hashable协议需要实现下面的内容，自定义相等及提供一个hashValue；
3.便于调试打印；

• 定义边

//1
enum EdgeType {
    case directed, undirected
}
//2
struct Edge<T: Hashable> {
    var source: Vertex<T>
    var destination: Vertex<T>
    var weight: Double?
}
//3
extension Edge: Hashable {
    var hashValue: Int {
        return "\(source)\(destination)\(weight ?? 0)".hashValue
    }
    
    static func == (lhs: Edge, rhs: Edge) -> Bool {
        return lhs.source == rhs.source &&
            lhs.destination == rhs.destination &&
            lhs.weight == rhs.weight
    }
}

1.因为图会根据边是否有方方向，分为有向图和无向图，所以先定义两种边的类型；
2.定义边结构，每个边都一个起点及终点，起点和终点就是顶点，同时边也可以有权重，也可以没有，所以定义一个可选型的weight变量；
3.同上面的同样道理，存储在字典中，需要可hash

• 邻接表
  下面我们创建一个新的类，这个类就是具体图的存储实现

class AdjacencyList<T: Hashable> {
    //1
    var adjacencyDic: [Vertex<T>: [Edge<T>]] = [:]
}

1.在类AdjacencyList中有一个adjacencyDic字典，这个字典就是用来存储图的，这个字典是 [Vertex<T>: [Edge<T>]] 类型，他的键名是图的顶点，而键值就是对应顶点的边的数组
ps: 这里也可以更简单的实现，将adjacencyDic 设置为 [Vertex<T>: [Vertex<T>]]类型，这里就没有边什么事了，键值中直接存储对应的邻居

下面我们可以在类AdjacencyList中，添加一些方法，比如新节点的创建，边的插入等等，但是我们也可以用一个更灵活的方式实现，通过协议来定义这些方法，然后让AdjacencyList来遵守实现，即我们统一定义好规则，这样就非常容易复用了。Swift中的协议真的是强大呀.......

创建图的操作接口协议

protocol Graphable {
    //1
    associatedtype Element: Hashable
    //2
    var description: CustomStringConvertible { get }
    //3
    func creatVertex(WithData data: Element) -> Vertex<Element>
    //4
    func addEdge(withType type: EdgeType, from source: Vertex<Element>, to destination: Vertex<Element>, with weight: Double?)
    //5
    func weight(from source: Vertex<Element>, to destination: Vertex<Element>) -> Double?
    //6
    func edges(from source: Vertex<Element>) -> [Edge<Element>]?
}

1.associatedtype 关键字 目的是在这里声明一个占位类型，来方便协议中后续的使用，这里定义了一个 需要遵守hash协议的 Element 泛型
2.便于调试
3.创建一个新的顶点，这里就用到了 我们前面定义的占位类型，Element就和 Vertex中的T是一样的
4.给两个节点添加一个边，可以是有向的，也可以是无向的
5.给边添加权重
6.获得某个顶点的所有的边

通过上面定义的接口实现图，代码如下：

extension AdjacencyList: Graphable {
    typealias Element = T
    
    var description: CustomStringConvertible {
        var result = ""
        for (vertex, edges) in adjacencyDic {
            var edgeStr = ""
            for (index, edge) in edges.enumerated() {
                if index != edges.count - 1 {
                    edgeStr.append("\(edge.destination) ,")
                }else {
                    edgeStr.append("\(edge.destination)")
                }
            }
            result.append("\(vertex) --> [ \(edgeStr) ]")
        }
        return ""
    }
    
    func creatVertex(WithData data: T) -> Vertex<T> {
        let vertex = Vertex(data: data)
        
        if adjacencyDic[vertex] == nil {
            adjacencyDic[vertex] = []
        }
        return vertex
    }
    
    func addEdge(withType type: EdgeType, from source: Vertex<T>, to destination: Vertex<T>, with weight: Double?) {
        if type == .directed {
            addDirectedEdge(from: source, to: destination, with: weight)
        }else {
            addUndirectedEdge(from: source, to: destination, with: weight)
        }
    }
    
    func weight(from source: Vertex<T>, to destination: Vertex<T>) -> Double? {
        guard let edges = adjacencyDic[source] else { return nil }
        for edge in edges {
            let _ = edge.destination == destination
            return edge.weight
        }
        return nil
    }
    
    func edges(from source: Vertex<T>) -> [Edge<T>]? {
        return adjacencyDic[source]
    }
    
    //添加有向边
    private func addDirectedEdge(from source: Vertex<T>, to destination: Vertex<T>, with weight: Double?) {
        let edge = Edge(source: source, destination: destination, weight: weight)
        adjacencyDic[source]?.append(edge)
    }
    //添加无向边
    private func addUndirectedEdge(from source: Vertex<T>, to destination: Vertex<T>, with weight: Double?) {
        let edge1 = Edge(source: source, destination: destination, weight: weight)
        let edge2 = Edge(source: destination, destination: source, weight: weight)
        adjacencyDic[source]?.append(edge1)
        adjacencyDic[source]?.append(edge2)
    }