【JS】数据结构之图结构

基本概念

什么是图？

• 图是一种数据结构，与树结构有些相似（在数学的概念上，树是图的一种）
• 树结构是一对多的关系，而图结构是多对多的关系
• 比如导航的最优路径：可以看成多个地点可以连接成好多条边，这是我们要找出耗时最少，路程最短的路径。

• 在图中，最基本的单元是顶点（相当于树中的节点），顶点之间的关系被称之为边。

• 按照连接的两个顶点的边的不同，可以把图分为以下几种：

无向图: 边没有方向的图，边的作用仅仅连接两个顶点，没有其他含义
有向图: 边不仅连接两个顶点，并且具有方向性，可以是单向也可以是双向的
带权图: 边可以指定权重
1
2
3

• 图的术语：

相邻顶点: 当两个顶点通过一条边相连时，我们称这两个顶点是相邻的，并且是依附这两个顶点的。
度: 某个顶点的度是依附于这个顶点的边的个数
子图: 一幅图中，所有的子集组成的图，包含这些边的依附的顶点。
路径: 是由边顺序连接的一系列的顶点组成
环: 是一条至少含有一条边且终点和起点相同的路径。
连通图: 如果图中，任意一个顶点度存在一条路径到达另外一个顶点，那这幅图我们就称之为连通图。
连通子图: 一个非联通图由若干个连通的部分组成，每一个连通的部分就可以称为该图的连通子图。
1
2
3
4
5
6
7

• 自环：即一条连接一个顶点和自身的边
• 平行边：连接同一对顶点的两条边（有可能是多条边）

图的实现

欧拉开创了新的学科：图论（数学的一个分支）

• 它以图为研究对象，研究顶点 和 边 组成的图形的数学理论和方法
• 主要研究的目的是事物之间的关系，顶点代表事物，边代表两个事物间的关系。

图是由顶点和边构成，所以图里面要存储的图形结构信息，无非是存储图的顶点和图的边。
顶点可以之间通过数组去存储，那边该通过什么存储呢？以该图为例

1. 邻接矩阵

矩阵是一个按照长方阵列排列的负数或实数集合。
N * M 数据的集合（九宫格）
去除表格线的九宫格就是矩阵的样式，矩阵是由行和列组成的一组数表。
邻接矩阵让每一个节点和整数相关联
用 1 表示顶点与顶点由直接的关系，用 0 表示没有连接。
1
2
3
4
5

2. 邻接表

• 图遍历思路：

1. 每一个顶点有三种状态
- 未发现（没有发现这个顶点）
- 已经发现（发现其他的顶点连接到这里，但是没有去查找这个顶点的全部连接的顶点）
- 已经探索（已经发现这个顶点连接的全部顶点）
2. 记录顶点是否被访问过，使用三种颜色来反映他们的状态
- 白色（未发现）
- 灰色（已经发现）
- 黑色（已经探索）
3. 广度优先遍历的过程
- 发现未发现顶点后，存放队列中，等待查找，并且并将这些顶点标记未发现
- 在队列中拿出已经发现的顶点，开始探索全部顶点，并且跳过已经探索的顶点
- 遍历完这个顶点以后，将这个顶点标志为已经探索
- 循环在队列中探索下一个顶点
4. 深度优先遍历的过程
- 从某一顶点开始查找，并将这个顶边标记为已经发现（灰色）
- 从这个顶点开始探索其他的全部的顶点，并跳过已经发现的顶点
- 变量为这个顶点以后，将这个顶点标记为已探索（黑色）
- 递归返回，继续探索下一个路径的最深顶点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 最短路径

1. 路径：由边顺序连接的顶点组成的
- 寻找最短路径，所谓路径指的是：
- 从图中某一个顶点（起点）到达另外一个顶点（终点）的路径
- 我们要找到一条路径使得沿这个路径边上的权值总和（路径长度）达到最小
2. 回溯点 
- 回溯点是离上一个顶点最近的点。A的回溯点是null，B的回溯点是A,E的回溯点是B
- 回溯路径（所有回溯点组成回溯路径）
const prev = {
	A: null,
	B: A,
	E: B,
	...
}
prev[E] = B	// E的回溯点是B
3. 常见的最短路径算法
- 迪杰斯特拉算法：是贪心算法的一个应用，用来解决单源点到其余顶点的最短路径的问题
- Floyd 算法： 经典的动态规划算法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 用JavaScript实现一个图结构：

// 队列
class Queue {
	constructor() {
		this.items = [];
	}
	enqueue(ele){
		this.items.push(ele);
	}
	dequeue() {
		return this.items.shift();
	}
	// 查看队列前端元素
	front(){
		return this.items[0];
	}
	// 查看队列后端元素
	rear(){
		return this.items[this.items.length - 1];
	}
	// 查看队列是否为空
	isEmpty(){
		return this.items.length === 0;
	}
	// 查看队列中元素个数
	size(){
		return this.items.length;
	}
	// 清空队列
	clear(){
		this.items = []
	}
}
// 栈
class Stack{
	constructor() {
		this.items = [];
	}
	// 入栈
	push(ele){
		this.items.push(ele);
	}
	// 出栈
	pop() {
		return this.items.pop();
	}
	// 获取栈顶元素
	peek(){
		return this.items[this.items.length - 1];
	}
	// 查看栈是否为空
	isEmpty(){
		return this.items.length === 0;
	}
	// 查看栈中元素个数
	size(){
		return this.items.length;
	}
	// 清空栈
	clear(){
		this.items = []
	}
}
// 存储顶点和边
class Graph {
	constructor() {
		// 顶点可以使用数组存储
		this.vertiecs = [];
		// 存储全部的边
		this.edgeList = {};
		/*
			A:['B','C','D']
		*/
	}
	addVerTex(v) {
		// 添加顶点
		this.vertiecs.push(v);
		// 存储边
		this.edgeList[v] = [];
	}
	// 添加边
	addEdge(a,b){
		// 无向图，实现：A与B相连接的同时，需要去实现B与A相连接
		this.edgeList[a].push(b);
		this.edgeList[b].push(a);
	}
	// 添加toString
	toString() {
		let rst = '';
		for(let i = 0; i<this.vertiecs.length; i++){
			// 顶点
			let vertex = this.vertiecs[i];
			rst += `${vertex}=>`;
			// 边
			let egde = this.edgeList[vertex];
			for(let j=0; j<egde.length; j++){
				rst += egde[j];
			}
			rst += '\n';
		}
		return rst;
	}
	// 初始化颜色
	/*
		- 白色（未发现）
		- 灰色（已经发现）
		- 黑色（已经探索）
	*/
	initColor(){
		let colors = {};
		for(let i=0; i<this.vertiecs.length; i++){
			// 所有的顶点颜色设置为白色
			colors[this.vertiecs[i]] = 'white';
		}
		return colors;
	}
	// 广度优先
	bfs(v,callback){
		// 将全部的顶点都设置为白色
		let color = this.initColor();
		// 创建队列
		let queue = new Queue();
		// 从 v 开始遍历
		queue.enqueue(v);
		// 所有的回溯点设置为null
		let prev = {};
		for(let i=0; i<this.vertiecs.length; i++){
			prev[this.vertiecs[i]] = null;
		}

		// 从队列中依次取出和放入数据
		while(!queue.isEmpty()){
			// A 出列
			const qVertex = queue.dequeue();
			// 获取 A 的所有边
			const edge = this.edgeList[qVertex];
			// 遍历所有的边
			for(let i=0; i<edge.length; i++){
				// 当前顶点
				const e = edge[i];
				if(color[e] === 'white'){
					// 未发现的顶点全部入列
					color[e] = 'gray';
					// 设置回溯点
					prev[e] = qVertex;
					// 顶点入列
					queue.enqueue(e)
				}
			}
			// A 已经探索，为黑色
			color[qVertex] = 'black';
			if(callback){
				callback(qVertex);
			}
		}
		return prev;
	}
	// 深度优先
	dfs(v,callback){
		const color = this.initColor();
		this.dfsVisit(v,color,callback);
	}
	// 递归实现深度优先
	dfsVisit(v,color,callback){
		// 修改颜色为灰色
		color[v] = 'gray';
		// 已经被访问到了
		if(callback){
			callback(v);
		}
		// 获取所有的边
		let edge = this.edgeList[v];
		// 遍历所有的边
		for(let i=0; i<edge.length; i++){
			// 当前边
			let e = edge[i];
			if(color[e] === 'white'){
				// 递归调用
				this.dfsVisit(e,color,callback);
			}
		}
		// 设置为黑色
		color[v] = 'black';
	}
}

const graph = new Graph();
// 添加顶点
graph.addVerTex('A');
graph.addVerTex('B');
graph.addVerTex('C');
graph.addVerTex('D');
graph.addVerTex('E');
graph.addVerTex('F');
// 添加边
graph.addEdge('A', 'B');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('A', 'C');
graph.addEdge('C', 'D');
graph.addEdge('A', 'D');

console.log('广度优先算法');
// 调用广度优先算法
graph.bfs('A',(e)=>{
	console.log(e);
})
console.log('深度优先算法');
// 调用深度优先算法
graph.dfs('A',(e)=>{
	console.log(e);
})


const prev = graph.bfs('A');
// 为了验证最短路径再添加一条边，图结构如下图所示，这条边的添加不会影响到上面算法打印的顺序
graph.addEdge('D','F');
// 测试最短路径
const shortPath = (from, to)=>{
	// 当前顶点
	let vertex = to;	// 设置当前顶点，找到当前顶点回溯点
	let stack = new Stack();
	while.(vertex!==from){
		stack.push(vertex);
		vertex = prev[vertex];	// 	寻找自己的回溯点
	}
	stack.push(vertex);
	let path = '';
	while(!stack.isEmpty()){
		path += `${stack.pop()}=>`;
	}
	path = path.slice(0,path.length-2);
	return path;
}
console.log("A 到 F 的最短路径",shortPath('A','F'))
console.log("A 到 D 的最短路径",shortPath('A','D'))
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235

• 最短路径图

• 总运行效果：