基本概念

什么是图？

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

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

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

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

• 图的术语：

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

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

图的实现

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

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

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

1. 邻接矩阵

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

2. 邻接表

• 图遍历思路：

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

• 最短路径

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

• 用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'))

• 最短路径图

• 总运行效果：