Swift4.2画”图”（Graph）

看看你需要啥：

• 一些编程基础
  
• 一台装了Xcode的mac或者装了SwiftPlayground的iPad
  
• 学习能力
  
• 没了
  
• 不，还有“图”是啥

30秒学会图

与图有关的概念

• 一个图是多个顶点与他们的连边的集合，因此我们只需要描述顶点和边
  
• 连边可以有方向，也可以没有，比如单行道
  
• 连边可以有权重，也可以没有，比如道路的距离

怎样实现图结构

• 顶点可以存储在数组或链表中
• 边可以存储在以顶点为head的链表中，也可以用二维数组表示顶点和边

我们开始了

我们的教学是渐进式的（

1. 认识链表
2. 描绘图的结构
3. 实现对图的遍历

认识链表

链表作为一种最基础的数据结构，实现了对多个元素线性的、动态的组织和管理，是实现图的基础之一。这里涉及到了类、模板、引用的知识。

链表上的结点类

class LinkedListNode<T> {
    var value:T
    var next:LinkedListNode?
    weak var previous:LinkedListNode?
    init(value:T){
        self.value = value
    }
}

weak关键字：weak声明previous是对被引用对象的弱引用，用于防止循环引用（互相被引用的对象无法释放）。例如A引用B，B引用A，因为他们都被引用，垃圾回收机制无法释放他们，但如果A对B的引用是弱引用，那么B没有被强引用，因而可以被直接释放，循环引用被破除。这里用来防止特定情况下的循环引用。

链表类

class LinkedList<T> {
    typealias Node = LinkedListNode<T>
    var head:Node?
}

描绘图的结构

我们知道，图可以用邻接矩阵或邻接表实现，这里采用邻接表实现图：一个存储结点的数组+n个扩展结点的链表（用于表达连边）。在Swift中，数组可以自由扩展，虽然和链表有很大区别，但我们用数组代替可以省很多事:-D。

存储结点的图

从链表结构转化

class Graph<T> {
    typealias Node = LinkedListNode<T>
    var nodes=[Node]()
}

顶点类

class graphNode<T> {
    var value:T
    var edges=[edge<T>]()
    init(value:T){
        self.value = value
    }
}

边类

class edge<T>{
    typealias node = graphNode<T>
    var vertex:node
    init(vertex:node){
        self.vertex=vertex
    }
}

添加顶点

class graph<T> {
    typealias node = graphNode<T>//用node代替graphNode比较简洁
    var nodes=[node]()//可以使用nodes.count
    func addNode(value:T) -> node {
        let newNode=node(value:value)//我们不需要更改结点内容，用lets表示常量
        nodes.append(newNode)
        return newNode
    }
}

添加边

class graph<T> {
    typealias node = graphNode<T>//用node代替graphNode比较简洁
    var nodes=[node]()//可以使用nodes.count
    func addNode(value:T) -> node {
        let newNode=node(value:value)//我们不需要更改结点内容，用lets表示常量
        nodes.append(newNode)
        return newNode
    }
    func addEdge(vertexA:node,vertexB:node) -> Bool {
        for n in vertexA.edges{//已经有边就不能再添加了
            if(n.vertex===vertexB){
                return false}
        }
        vertexA.edges.append(edge(vertex:vertexB))
        vertexB.edges.append(edge(vertex:vertexA))
        return true
    }
}

实现对图的遍历

深度优先遍历

我们只实现深度优先遍历，实现思路：从出发点开始，选择一个未访问过的邻居，递归下去，所有邻居都被访问时返回。为了区别，我们向顶点类添加visited属性。

class graph<T> {
    typealias node = graphNode<T>//用node代替graphNode比较简洁
    var nodes=[node]()//可以使用nodes.count
    func addNode(value:T) -> node {
        let newNode=node(value:value)//我们不需要更改结点内容，用lets表示常量
        nodes.append(newNode)
        return newNode
    }
    func addEdge(vertexA:node,vertexB:node) -> Bool {
        for v in vertexA.edges{//已经有边就不能再添加了
            if(v.vertex===vertexB){
                return false}
        }
        vertexA.edges.append(edge(vertex:vertexB))
        vertexB.edges.append(edge(vertex:vertexA))
        return true
    }
    func DFS(start:node) -> Void {
        for v in start.edges {
            if(v.vertex.visited==false){
                proc(v:v.vertex)
                DFS(start: v.vertex)
            }
        }
        return
    }
    func proc(v:node) -> Void{
        v.visited=true
        //对顶点进行的操作
    }
}

class graphNode<T> {
    var value:T
    var edges=[edge<T>]()
    init(value:T){
        self.value = value
    }
    var visited = false
}

class edge<T>{
    typealias node = graphNode<T>
    var vertex:node
    init(vertex:node){
        self.vertex=vertex
    }
}

//验证性操作
var G = graph<Int>()
var v1=G.addNode(value:5)
var v2=G.addNode(value: 10)
G.addEdge(vertexA: v1, vertexB: v2)
G.nodes[0]
G.nodes[1]
G.DFS(start: v1)
G.nodes[0]
G.nodes[1]