数据结构笔记—图

图的定义和基本术语

图的知识图谱

 Graph=(V,E)
V:顶点(数据元素)的有穷非空集合,和 E:边的有穷集合组成

有向图:每条边都是有方向的

无向图: 每条边都是无方向的

完全图:任意两个点都有一条边相连

稀疏图:有很少边或弧的图。

稠密图:有较多边或弧的图。

:边/弧带权的图。

邻接:有边/弧相连的两个顶点之间的关系。
存在(vi, vj),则称vi和vj互为邻接点;
存在<vi, vj>,则称vi邻接到vj, vj邻接于vi

关联(依附):边/弧与顶点之间的关系。
存在(vi, vj)/ <vi, vj>, 则称该边/弧关联于vi和vj

顶点的度:与该顶点相关联的边的数目,记为TD(v)。在有向图中, 顶点的度等于该顶点的入度与出度之和。
顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v)
顶点 v 的出度是以 v 为始点的有向边的条数, 记作OD(v)

路径:接续的边构成的顶点序列。

路径长度:路径上边或弧的数目/权值之和。

回路(环):第一个顶点和最后一个顶点相同的路径。
1
简单路径:顶点不重复出现的路径。

简单回路(简单环):除路径起点和终点相同外,其余顶点均不相同的路径。

连通图(强连通图) 在无(有)向图G=( V, {E} )中,若对任何两个顶点 v、u 都存在从v 到 u 的路径,则称G是连通图(强连通图)。

权与网 图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。带权的图称为网。

子图 设有两个图G=(V,{E})、G1=(V1,{E1}),若V1包含于 V,E1 包含于 E,则称 G1是G的子图。

图的存储结构

顺序存储结构:

 数组表示法(邻接矩阵)

邻接矩阵表示法的特点

优点:容易实现图的操作,如:求某顶点的度、判断顶点之间是否有边、找顶点的邻接点等等。

缺点:n个顶点需要n*n个单元存储边;空间效率为O(n2)。 对稀疏图而言尤其浪费空间。

链式存储结构:

邻接表表示法的特点

优点:空间效率高,容易寻找顶点的邻接点;

缺点:判断两顶点间是否有边或弧,需搜索两结点对应的单链表,没有邻接矩阵方便。

多重链表

  1. 邻接表:

  2. 邻接多重表:

  3. 十字链表:

邻接矩阵与邻接表表示法的关系

联系:邻接表中每个链表对应于邻接矩阵中的一行,链表中结点个数等于一行中非零元素的个数。

区别

① 对于任一确定的无向图,邻接矩阵是唯一的(行列号与顶点编号一致),但邻接表不唯一(链接次序与顶点编号无关)。

② 邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。

用途:邻接矩阵多用于稠密图;而邻接表多用于稀疏图

图的实现

 链式存储结构

1
2
3
4
5
6
7
8
9
       第一
/ /\ \ 1
6 / / \ \
第四 /5 \3 第二
\ / \ |
7\ / \ |2
第五 ---4--- 第三


定义一个顶点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public struct Vertex<T:Hashable> {
var data :T
}

extension Vertex:Hashable {

public var hashValue: Int {
return "\(data)".hashValue
}

static public func == (lhs:Vertex,rhs:Vertex) -> Bool {
return lhs.data == rhs.data
}

}

extension Vertex: CustomStringConvertible {
public var description: String {
return "\(data)"
}
}

定义边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public enum EdgeType {
case directed // 有方向的
case undirected // 无方向的
}

public struct Edge<T:Hashable> {
public var source:Vertex<T> //原点
public var destination:Vertex<T>//目的地
public let weight: Double? //权重
}

extension Edge :Hashable {

public var hashValue: Int {
return "\(source)\(destination)\(weight)".hashValue
}

static public func == (lhs:Edge<T>,rhs:Edge<T>) -> Bool {
return lhs.source == rhs.source && lhs.destination == rhs.destination && lhs.weight == rhs.weight
}

}

定义协议

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
protocol Graphable {
//协议需要一个称为元素的关联类型。这允许协议是通用的,可以容纳任何类型。
associatedtype Element: Hashable //
//为了让使用者定义一个输出的格式
var description: CustomStringConvertible { get } // 2
//提供一个通用的方法生成一个顶点
func createVertex(data: Element) -> Vertex<Element> // 3
//提供一个通用的方法 在两个顶点之间添加一条边
func add(_ type: EdgeType, from source: Vertex<Element>, to destination: Vertex<Element>, weight: Double?)
//获取两个顶点之间的权重
func weight(from source: Vertex<Element>, to destination: Vertex<Element>) -> Double?
// 获取与顶点相连的所有的边
func edges(from source: Vertex<Element>) -> [Edge<Element>]? // 6

}

定义一个表实现协议

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
open class AdjacencyList<T: Hashable> {
// adjacencyDict 是一个字典 key 是顶点 value 是于顶点相连的所有边
public var adjacencyDict : [Vertex<T>: [Edge<T>]] = [:]
public init() {}

/// 添加一个有方向的边
///
/// - Parameters:
/// - source: 顶点
/// - destination: 终点
/// - weight: 权重
fileprivate func addDirectedEdge(from source: Vertex<Element>, to destination: Vertex<Element>, weight: Double?) {
let edge = Edge(source: source, destination: destination, weight: weight) // 1
adjacencyDict[source]?.append(edge) // 2
}

/// 添加一个无方向的边:无论是源点或者是终点,其对应的边点数组都要添加这条边
///
/// - Parameters:
/// - vertices: 源点和终点
/// - weight: 权重
fileprivate func addUndirectedEdge(vertices: (Vertex<Element>, Vertex<Element>), weight: Double?) {
let (source, destination) = vertices
addDirectedEdge(from: source, to: destination, weight: weight)
addDirectedEdge(from: destination, to: source, weight: weight)
}
}


extension AdjacencyList:Graphable {
public typealias Element = T
//为了让使用者定义一个输出的格式
public var description: CustomStringConvertible {
var result = ""
for (vertex, edges) in adjacencyDict {
var edgeString = ""
for (index, edge) in edges.enumerated() {
if index != edges.count - 1 {
edgeString.append("\(edge.destination), ")
} else {
edgeString.append("\(edge.destination)")
}
}
result.append("\(vertex) ---> [ \(edgeString) ] \n ")
}
return result
} // 2
//提供一个通用的方法生成一个顶点
public func createVertex(data: Element) -> Vertex<Element> {
let vertex = Vertex(data: data) //生成一个顶点
if adjacencyDict[vertex] == nil { //如果当前存储边的数组为 nil(即还没有初始化) 则生成一个数组
adjacencyDict[vertex] = []
}
return vertex //返回顶点
}
//提供一个通用的方法 在两个顶点之间添加一条边
public func add(_ type: EdgeType, from source: Vertex<Element>, to destination: Vertex<Element>, weight: Double?) {
switch type {
case .directed://有向图
addDirectedEdge(from: source, to: destination, weight: weight)
break
case .undirected://无向图
addUndirectedEdge(vertices: (source, destination), weight: weight)
break
}

}
//获取两个顶点之间的权重
public func weight(from source: Vertex<Element>, to destination: Vertex<Element>) -> Double? {
//获取当前源点的所有边
guard let edges = adjacencyDict[source] else { return nil }
for edge in edges {// 遍历所有边
if edge.destination == destination {//如果当前边的目的地等于要查询的目的地
return edge.weight //则返回 权重
}
}
return nil
}
// 获取与顶点相连的所有的边
public func edges(from source: Vertex<Element>) -> [Edge<Element>]? {
return adjacencyDict[source]
}
}

使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
let list = AdjacencyList<String>.init()

let first = list.createVertex(data: "第一")
let second = list.createVertex(data: "第二")
let third = list.createVertex(data: "第三")
let forth = list.createVertex(data: "第四")
let fifth = list.createVertex(data: "第五")

list.add(.undirected, from: first, to: second, weight: 1)
list.add(.undirected, from: first, to: third, weight: 3)
list.add(.undirected, from: first, to: forth, weight: 6)
list.add(.undirected, from: first, to: fifth, weight: 5)
list.add(.undirected, from: forth, to: fifth, weight: 7)
list.add(.undirected, from: fifth, to: third, weight: 4)
list.add(.undirected, from: second, to: third, weight: 2)

print(list.description)

结果:

第四 ---> [ 第一, 第五 ]
第一 ---> [ 第二, 第三, 第四, 第五 ]
第五 ---> [ 第一, 第四, 第三 ]
第三 ---> [ 第一, 第五, 第二 ]
第二 ---> [ 第一, 第三 ]


//print(list.edges(from: third))
print(list.weight(from: third, to: fifth) ?? 0)

结果:
4.0

图的遍历

定义

 从已给的连通图中某一顶点出发,沿着一些边访遍图中所有的顶点,且使每个顶点仅被访问一次,就叫做图的遍历,它是图的基本运算。

遍历实质

 找每个顶点的邻接点的过程。

图的特点

 图中可能存在回路,且图的任一顶点都可能与其它顶点相通,在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。

图常用的遍历:

深度优先搜索

 仿树的先序遍历过程

简单归纳:

  1. 访问起始点v;
  2. 若v的第1个邻接点没访问过,深度遍历此邻接点;
  3. 若当前邻接点已访问过,再找v的第2个邻接点重新遍历。

深度优先搜索算法实现

 与广度优先搜索算法不同的是广度优先算法需要一个队列作铺助,而广度优先搜索算法需要一个栈,因为栈是先进后出,深度优先搜索算法需要实现回退的逻辑,而栈正好符合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public func depthFirstSearch(from source: Vertex<Element>, to destination: Vertex<Element>)
-> [Edge<Element>]? {
// 之所以用队列的原因就是 深度优先算法需要回退
var stack = Stack<Vertex<Element>>() // 创建一个堆栈来存储从起点到终点的潜在路径。
stack.push(source)//把开始的顶点压入栈
var visits : [Vertex<Element> : Visit<Element>] = [source: .source]//存储已经访问过的顶点
while let vertex = stack.pop() {
if vertex == destination { // 如果源点和终点相同
var vertex = destination //
var route: [Edge<Element>] = []// 访问的路径
while let visit = visits[vertex],
case .edge(let edge) = visit {
route = [edge] + route
vertex = edge.source
}
return route
}

guard let neighbors = self.edges(from: vertex), neighbors.count > 0 else {
_ = stack.pop()
continue
}

for edge in neighbors {
if visits[edge.destination] == nil {
stack.push(edge.destination)
visits[edge.destination] = .edge(edge)
}
}
}
return nil
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
上文中的图用深度优先算法搜索 原点是“第五” 终点是“第二”

if let ed = list.depthFirstSearch(from: fifth, to: second) {
print("深度优先")
for edge in ed {
print("\(edge.source) -> \(edge.destination)")
}
}


结果是:

深度优先
第五 -> 第三
第三 -> 第二

DFS算法效率分析

  1. 用邻接矩阵来表示图,遍历图中每一个顶点都要从头扫描该顶点所在行,时间复杂度为O(n2)。
  2. 用邻接表来表示图,虽然有 2e 个表结点,但只需扫描 e 个结点即可完成遍历,加上访问 n个头结点的时间,时间复杂度为O(n+e)。

结论:
稠密图适于在邻接矩阵上进行深度遍历;
稀疏图适于在邻接表上进行深度遍历。

广度优先搜索

 基本思想:——仿树的层次遍历过程

步骤简单归纳:

1.在访问了起始点v之后,依次访问 v的邻接点;

2.然后再依次访问这些顶点中未被访问过的邻接点;
直到所有顶点都被访问过为止。

代码实现以及步骤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
  public func breadthFirstSearch(from source: Vertex<Element>, to destination: Vertex<Element>)
-> [Edge<Element>]? {
var queue = GraphaQueue<Vertex<Element>>()
queue.enqueue(source) // 1先把源点加入队列
/*
用字典 记录已经访问过的顶点用于记录访问的路径
键:顶点
值:一个枚举值
enum Visit<Element: Hashable> {
case source 原点
case edge(Edge<Element>) 边
}
*/
var visits : [Vertex<Element> : Visit<Element>] = [source: .source]
while let visitedVertex = queue.dequeue() { // 2遍历取出然后取出出队的元素
if visitedVertex == destination { // 3如果源点和终点相同
var vertex = destination //
var route: [Edge<Element>] = []// 访问的路径

while let visit = visits[vertex],
case .edge(let edge) = visit {
route = [edge] + route
vertex = edge.source

}
return route
}
/*
1 取出跟原点相关的所有边
2 遍历跟原点相关的所有边 --> 找到边的终点
3 判断:如果边的终点没有被访问过:即邻接点还没有被访问过
4 把此邻接点加入队列
5 把邻接点标记为已访问
*/
let neighbourEdges = edges(from: visitedVertex) ?? [] // 1
for edge in neighbourEdges {//2
if visits[edge.destination] == nil {//3
queue.enqueue(edge.destination)//4
visits[edge.destination] = .edge(edge)//5
}
print("\(edge.destination)")
}
print("---end---\n")
}
return nil
}
1
2
3
4
5
6
7
8
9
10
11
12
13
上文中的图用广度优先搜索,原点是“第五” 终点是“第二”

if let ed = list.breadthFirstSearch(from: fifth, to: second) {
print("广度优先")
for edge in ed {
print("\(edge.source) -> \(edge.destination)")
}
}
结果:

广度优先
第五 -> 第一
第一 -> 第二
  • 注意:同样是从“第五”到“第二”,广度优先算法和深度优先算法的结果是不同的

总结:广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有回退的情况。
因此,广度优先搜索不是一个递归的过程,其算法也不是递归的。

广度优先算法效率分析

  • 如果使用邻接矩阵,则BFS对于每一个被访问到的顶点,都要循环检测矩阵中的整整一行( n 个元素),总的时间代价为O(n2)。
  • 用邻接表来表示图,虽然有 2e 个表结点,但只需扫描 e 个结点即可完成遍历,加上访问 n个头结点的时间,时间复杂度为O(n+e)。

广度优先与深度优先算法效率比较

  • 空间复杂度相同,都是O(n)(借用了堆栈或队列);

  • 时间复杂度只与存储结构(邻接矩阵或邻接表)有关,而与搜索路径无关。

图的应用

最小生成树

极小连通子图:该子图是G 的连通子图,在该子图中删除任何一条边,子图不再连通。

生成树:包含图G所有顶点的极小连通子图(n-1条边)。

最小生成树的典型用途

 欲在n个城市间建立通信网,则n个城市应铺n-1条线路;但因为每条线路都会有对应的经济成本,而n个城市可能有n(n-1)/2 条线路,那么,如何选择n–1条线路,使总费用最少?

首先明确:
使用不同的遍历图的方法,可以得到不同的生成树
从不同的顶点出发,也可能得到不同的生成树。
按照生成树的定义,n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。

 目标:
在网的多个生成树中,寻找一个各边权值之和最小的生成树

构造最小生成树的准则

  • 必须只使用该网中的边来构造最小生成树;
  • 必须使用且仅使用n-1条边来联结网络中的n个顶点
  • 不能使用产生回路的边

如何求最小生成树

Prim算法:

 归并顶点,与边数无关,适于稠密网

代码实现: 要依赖一个优先队列(堆)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Prim<T:Hashable> {

typealias Graph = AdjacencyList<T>
//定义一个小堆
var heap = Heap<(vertex:Vertex<T>,weight:Double,parent:Vertex<T>?)>.init { (vertex, vertex2) -> Bool in
return vertex.weight < vertex2.weight
}

/// 生成最小生成树
///
/// - Parameter graph: <#graph description#>
/// - Returns: <#return value description#>
func createMinimumSpanningTree(graph:Graph) -> (cost:Double,mst:Graph) {
var cost = 0.0
let mst = Graph()
var visited = Set<Vertex<T>>()

guard let start = graph.getAllVertices().first else{
print(mst.description)
return (cost:cost,mst:mst)
}
//先把开始的顶点加入到堆中
heap.enqueue((vertex: start, weight: 0.0, parent: nil))

while let head = heap.dequeue() {
let vertex = head.vertex //取出堆中的第一个顶点
if visited.contains(vertex) {//检查是否已经访问过了 如果已经访问过了 则进行下一次循环
continue
}
visited.insert(vertex)
cost += head.weight
if let prev = head.parent { // 5
print(prev.description)
let pre = mst.createVertex(data: prev.data)
let ver = mst.createVertex(data: vertex.data)
mst.add(.undirected, from: pre, to: ver, weight: head.weight)
}

if let neighbours = graph.edges(from: vertex) {
for neighbour in neighbours {
if !visited.contains(neighbour.destination) {
heap.enqueue((vertex: neighbour.destination, weight: neighbour.weight ?? 0, parent: vertex))
}
}
}
}
return (cost:cost,mst:mst)
}
}

测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
let list = AdjacencyList<String>.init()

let first = list.createVertex(data: "第一")
let second = list.createVertex(data: "第二")
let third = list.createVertex(data: "第三")
let forth = list.createVertex(data: "第四")
let fifth = list.createVertex(data: "第五")

list.add(.undirected, from: first, to: second, weight: 1)
list.add(.undirected, from: first, to: third, weight: 3)
list.add(.undirected, from: first, to: forth, weight: 6)
list.add(.undirected, from: first, to: fifth, weight: 5)
list.add(.undirected, from: forth, to: fifth, weight: 7)
list.add(.undirected, from: fifth, to: third, weight: 4)
list.add(.undirected, from: second, to: third, weight: 2)


let prim = Prim<String>.init()
let (cost,mst) = prim.createMinimumSpanningTree(graph: list)

print("权值:\(cost)")
print("最小生成树:")

print(mst.description)

结果:

权值:13.0
最小生成树:
第四 ---> [ 第一 ]
第一 ---> [ 第四, 第二 ]
第五 ---> [ 第三 ]
第三 ---> [ 第二, 第五 ]
第二 ---> [ 第一, 第三 ]

Kruskal算法

 归并边,适于稀疏网

最短路径

典型用途: 交通问题。如:城市A到城市B有多条线路,但每条线路的交通费(或所需时间)不同,那么,如何选择一条线路,使总费用(或总时间)最少?

问题抽象: 在带权有向图中A点(源点)到达B点(终点)的多条路径中,寻找一条各边权值之和最小的路径,即最短路径。

  • 注意:最短路径与最小生成树不同,路径上不一定包含n个顶点

两种常见的最短路径问题:

单源最短路径—用Dijkstra(迪杰斯特拉)算法

 一顶点到其余各顶点

所有顶点间的最短路径—用Floyd(弗洛伊德)算法

 任意两顶点之间

拓扑排序

解决的问题

 用有向图来描述一个工程或系统的进行过程。
一个工程可以分为若干个子工程,只要完成了这些子工程(活动),就可以导致整个工程的完成。

拓扑排序算法的思想-重复选择没有直接前驱的顶点

  1. 输入AOV网络。令 n 为顶点个数。
  2. 在AOV网络中选一个没有直接前驱的顶点, 并输出之;
  3. 从图中删去该顶点, 同时删去所有它发出的有向边;
  4. 重复以上 2、3 步, 直到:

 1>全部顶点均已输出,拓扑有序序列形成,拓扑排序完成

 2>图中还有未输出的顶点,但已跳出处理循环。这说明图中还剩下一些顶点,它们都有直接前驱,再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。

关键路径

解决的问题

  假设以有向网表示一个施工流图,弧上的权值表示完成该项子工程所需时间。
问:哪些子工程项是“关键工程”?
即:哪些子工程项将影响整个工程的完成期限的。

 整个工程完成的时间为:从有向图的源点到汇点的最长路径。

 关键活动指的是:该弧上的权值增加 将使有向图上的最长路径的长度增加。

未完待续。。。

坚持原创,您的支持将鼓励我继续创作!