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]

发表评论

电子邮件地址不会被公开。