我们的教学是渐进式的(
链表作为一种最基础的数据结构,实现了对多个元素线性的、动态的组织和管理,是实现图的基础之一。这里涉及到了类、模板、引用的知识。
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]