图的定义
图就是由若干个顶点和边连接起来的一种结构。很多东西都可以用图来说明，例如人际关系，或者地图。
其中图还分为有向图和无向图。
如下就是有向图
图的数据结构
对于图这种关系，可以通过两种方式来存储。
领接表
将每个顶点与其相邻的顶点存储起来。
邻接矩阵
将顶点间的相邻关系用0和1来表示，0表示不相邻，1表示相邻。
图的实现
如下采用邻接表结构实现。
构造函数
class Graph {
constructor() {
this.vertices = [];
this.adjList = new Map();
}
}
verrices存储所有的顶点，adjList存储顶点间的关系。
增
addVertex(v) {
this.vertices.push(v);{1}
this.adjList.set(v, []);{2}
}
addEdge(v, w) {
this.adjList.get(v).push(w);
this.adjList.get(w).push(v);
}
addVertex函数为新增顶点。{2}是为新增的顶点初始化一个为空的邻接点。
addEdge函数为关联两个顶点为邻接点。由于本次示例的是无向图，因此每个顶点都互相增加为邻接点。
遍历
图的遍历分为广度优先遍历和深度优先遍历。
广度优先遍历就是从一个顶点开始，一层一层的遍历顶点。而深度优先遍历，是从一个顶点开始，选择一个路径一直深入遍历，直到到达该路径的尽头，再返回去，按照同样的方式，遍历其他顶点。
无论广度优先还是深度优先，大致原理都是，创建一个字段，从一个顶点开始，将其邻接点一个个存入该字段中，唯一的区别是，广度优先遍历，该字段用队列存储，而深度优先遍历用栈存储。
然而由于本次示例的图为无向图，会出现重复遍历的情况，例如A顶点的邻接点有B，B的邻接点有A。因此需要创建一个类，来维护这些顶点哪些已经被遍历过了，哪些还没有遍历。
class GraphStatus {
constructor() {
this.status = {};
}
detect(key) {
this.status[key] = true;
}
isDetected(key) {
return !!this.status[key];
}
}
如下是广度优先遍历
bfs(v, cb) {
const queue = [],
graphStatus = new GraphStatus();
queue.push(v);
while (queue.length > 0) {
const u = queue.shift();
graphStatus.detect(u);
this.adjList.get(u).forEach(item => {
if (!graphStatus.isDetected(item)) {
graphStatus.detect(item);
queue.push(item);
}
});
if (cb) {
cb(u);
}
}
}
如下是深度优先遍历
dfs(v, cb) {
const stack = [],
colorStatus = new GraphStatus();
stack.push(v);
while (stack.length > 0) {
const u = stack.pop();
colorStatus.detect(u);
this.adjList.get(u).forEach(item => {
if (!colorStatus.isDetected(item)) {
colorStatus.detect(item);
stack.push(item);
}
});
cb(u);
}
}
最短路径
基于广度优先遍历，可以很轻易的算出最短路径。
findDepth(v) {
let queue = [],
colorStatus = new GraphStatus(),
vPath = { [v]: [v] },
vDepth = {},
depth = 0;
queue.push(v);
while (queue.length > 0) {
depth++;
const u = queue.shift();
colorStatus.detect(u);
// 相邻顶点
const edgeVertex = this.adjList.get(u);
edgeVertex.forEach(item => {
if (!colorStatus.isDetected(item)) {
// 深度统计
vDepth[item] = depth;
// 路径统计
vPath[item] = [...vPath[u], item];
colorStatus.detect(item);
queue.push(item);
}
});
}
return { depth: vDepth, path: vPath };
}
