看看你需要啥：
- 一些编程基础
- 一台装了Xcode的mac或者装了SwiftPlayground的iPad
- 学习能力
- 没了
- 不，还有“图”是啥
30秒学会图
与图有关的概念
- 一个图是多个顶点与他们的连边的集合，因此我们只需要描述顶点和边
- 连边可以有方向，也可以没有，比如单行道
- 连边可以有权重，也可以没有，比如道路的距离
怎样实现图结构
- 顶点可以存储在数组或链表中
- 边可以存储在以顶点为head的链表中，也可以用二维数组表示顶点和边
我们开始了
我们的教学是渐进式的（
- 认识链表
- 描绘图的结构
- 实现对图的遍历
认识链表
链表作为一种最基础的数据结构，实现了对多个元素线性的、动态的组织和管理，是实现图的基础之一。这里涉及到了类、模板、引用的知识。
链表上的结点类
代码语言：javascript复制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没有被强引用，因而可以被直接释放，循环引用被破除。这里用来防止特定情况下的循环引用。
链表类
代码语言：javascript复制class LinkedList<T> {
typealias Node = LinkedListNode<T>
var head:Node?
}描绘图的结构
我们知道，图可以用邻接矩阵或邻接表实现，这里采用邻接表实现图：一个存储结点的数组 n个扩展结点的链表（用于表达连边）。在Swift中，数组可以自由扩展，虽然和链表有很大区别，但我们用数组代替可以省很多事:-D。
存储结点的图
从链表结构转化
代码语言：javascript复制class Graph<T> {
typealias Node = LinkedListNode<T>
var nodes=[Node]()
}顶点类
代码语言：javascript复制class graphNode<T> {
var value:T
var edges=[edge<T>]()
init(value:T){
self.value = value
}
}边类
代码语言：javascript复制class edge<T>{
typealias node = graphNode<T>
var vertex:node
init(vertex:node){
self.vertex=vertex
}
}添加顶点
代码语言：javascript复制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
}
}添加边
代码语言：javascript复制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属性。
代码语言：javascript复制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]
