学习背景
53685A7D-8753-4F2F-A8D6-DB24C846A29A.png
工作中某块需求涉及到查找两点之间全部路径的需求，尝试利用图的算法来解决这一问题。
目标：找出途中从开始到结束节点中间的所有路径
概念
图是网络结构的抽象模型。图是一组由边连接的节点（或顶点），任何二元关系都可以用图来表示。
一个图G=(V, E)由以下兀素组成：
- V: 一组顶点
- E: 一组边，连接V中的顶点
概念图.png
由一条边连接在一起的顶点称为相邻顶点 比如，A和B是相邻的
一个顶点的度是其相邻顶点的数量 比如，A和其他三个顶点相连接，因此，A的度为3
路径是顶点v1, v2, ...vk的一个连续序列 以上图为例， 其中包含路径A B E I 和 A C D G。
图的两种存储结构
乍看起来，图和树或者二叉树很像，我们可能会尝试用树的方式来创建一个图类，用节点来表示每个顶点。但这种情况下，如果用基于对象的方式去处理就会有问题，因为图可能增长到非常大。 用对象来表示图很快会变得效率低下，所以我们要考虑表示顶点或边的其他方案。
用例：
// 顶点个数
var point = 10;
// 相连节点
var line = [
[1, 2], [1, 5], [1, 9], [2, 8],[3, 7], [4, 5],[5, 8], [5, 9],[7, 9], [8, 7], [9, 1], [9, 2]
];
1.邻接矩阵：（Adjacency Matrix）适用于稠密图（完全图）
图最常见的实现是邻接矩阵。每个节点都和一个整数相关联，该整数将作为数组的索引。我 们用一个二维数组来表示顶点之间的连接。
function MatrixGraph(n, direction) {
this.n = n;
this.m = 0;
this.direction = false;
this.g = Array(n)
.fill(1)
.map(() => {
return Array(n)
.fill(1)
.map(() => {
return 0;
});
});
}
MatrixGraph.prototype.addEdge = function(x, y) {
if (x < this.n && y < this.n && !this.hasEdge(x, y)) {
this.g[x][y] = 1;
this.m++;
}
};
MatrixGraph.prototype.printG = function() {
let sum = "";
console.log("this.g: ", this.g);
this.g.forEach((item, i) => {
item.forEach(p => {
sum += ` ${p}`;
});
sum += `\n`;
});
console.log(sum);
};
MatrixGraph.prototype.hasEdge = function(x, y) {
return this.g[x][y];
};
var graph = new DenseGraph(point, false);
line.forEach(item => {
graph.addEdge(item[0], item[1]);
});
graph.printG()；
// 生成的邻接矩阵：
// 0 0 0 0 0 0 0 0 0 0
// 0 0 1 0 0 1 0 0 0 1
// 0 0 0 0 0 0 0 0 1 0
// 0 0 0 0 0 0 0 1 0 0
// 0 0 0 0 0 1 0 0 0 0
// 0 0 0 0 0 0 0 0 1 1
// 0 0 0 0 0 0 0 0 0 0
// 0 0 0 0 0 0 0 0 0 1
// 0 0 0 0 0 0 0 1 0 0
// 0 1 1 0 0 0 0 0 0 0
2.邻接表（Adjacency Lists）适用于稀疏图
邻接表是图的一种链式存储结构，对于图G中的每个顶点Vi，把所有邻接于Vid 顶点Vj连成一个单链表，这个单链表称为顶点Vi的邻接表
function ChainGraph(n, direction) {
this.n = n;
this.m = 0;
this.direction = false;
this.g = {};
}
ChainGraph.prototype.addEdge = function(x, y) {
if (!this.hasEdge(x, y)) {
this.g[x] ? this.g[x].push(y) : (this.g[x] = [y]);
this.m++;
}
};
ChainGraph.prototype.printG = function() {
let sum = "";
Object.keys(this.g).forEach((key, i) => {
sum += key + ":";
this.g[key].forEach(p => {
sum += ` ${p}`;
});
sum += `\n`;
});
console.log(sum);
};
ChainGraph.prototype.hasEdge = function(x, y) {
if (!this.g[x]) this.g[x] = [];
if (!this.g[y]) this.g[y] = [];
return this.g[x] && this.g[x].includes(y);
};
var graph = new SparseGraph(point, false);
line.forEach(item => {
graph.addEdge(item[0], item[1]);
});
graph.printG();
//生成的邻接表：
//0
//1 2 5 9
//2 8
//3 7
//4 5
//5 8 9
//6
//7 9
//8 7
//9 1 2
图的两种遍历方法
和树数据结构类似，我们可以访问图的所有节点。有两种算法可以对图进行遍历：
- 深度优先搜索（Depth-First Search，DFS)
深度优先搜索DFS遍历类似于树的前序遍历。其基本思路是：
a) 假设初始状态是图中所有顶点都未曾访问过，则可从图G中任意一顶点v为初始出发点，首先访问出发点v，并将其标记为已访问过。
b)然后依次从v出发搜索v的每个邻接点w，若w未曾访问过，则以w作为新的出发点出发，继续进行深度优先遍历，直到图中所有和v有路径相通的顶点都被访问到。
c) 若此时图中仍有顶点未被访问，则另选一个未曾访问的顶点作为起点，重复上述步骤，直到图中所有顶点都被访问到为止。
ChainGraph.prototype.deepFirstSearch = function() {
// 存放遍历结果
var pointList = [];
const dfs = arr => {
arr.forEach(key => {
if (pointList.includes(key)) return;
pointList.push(key);
dfs(this.g[key]);
});
};
dfs(Object.keys(this.g));
console.log(pointList); //["A", "B", "D", "I", "C", "E", "G", "F", "H"]
};
- 广度优先搜索（Breadth-First Search，BFS)
广度优先搜索遍历BFS类似于树的按层次遍历。其基本思路是：
a) 首先访问出发点Vi
b) 接着依次访问Vi的所有未被访问过的邻接点Vi1，Vi2，Vi3，…，Vit并均标记为已访问过。
c) 然后再按照Vi1，Vi2，… ，Vit的次序，访问每一个顶点的所有未曾访问过的顶点并均标记为已访问过，依此类推，直到图中所有和初始出发点Vi有路径相通的顶点都被访问过为止。
SparseGraph.prototype.breadthFirstSearch = function() {
// 存放遍历结果
var pointList = [];
var pendingList = [Object.keys(this.g)[0]];
const bfs = () => {
var curPoint = pendingList.shift();
if (!pointList.includes(curPoint)) pointList.push(curPoint);
pendingList = pendingList.concat(this.g[curPoint]);
if (pendingList.length) bfs();
};
bfs();
console.log(pointList); //["A", "B", "C", "D", "E", "F", "I", "G", "H"]
};
找出开始到结束节点的所有通路
1.将图抽象成用例
var point = 10;
// 相连节点
var line = [
[1, 2], [1, 5], [1, 9], [2, 8],[3, 7], [4, 5],[5, 8], [5, 9],[7, 9], [8, 7], [9, 1], [9, 2]
];
2生成邻接矩阵
// 0 0 0 0 0 0 0 0 0 0
// 0 0 1 0 0 1 0 0 0 1
// 0 0 0 0 0 0 0 0 1 0
// 0 0 0 0 0 0 0 1 0 0
// 0 0 0 0 0 1 0 0 0 0
// 0 0 0 0 0 0 0 0 1 1
// 0 0 0 0 0 0 0 0 0 0
// 0 0 0 0 0 0 0 0 0 1
// 0 0 0 0 0 0 0 1 0 0
// 0 1 1 0 0 0 0 0 0 0
3获取所有路径
DenseGraph.prototype.getAllPath = function() {
const newBilityPath = [];
const getPath = (path, arr) => {
let has = false;
const newPath = [...path];
for (let i = 0; i < arr.length; i++) {
if (arr[i]) {
//有连接
if (has) {
newPath.pop();
}
newPath.push(i);
getPath(newPath, this.g[i]);
has = true;
}
}
if (!has) {
newBilityPath.push(newPath);
}
};
// 路径查找
getPath([0], this.g[0]);
console.log("newBilityPath: ", newBilityPath);
};
graph.getAllPath();
//0: (4) [0, 1, 3, 8]
//1: (5) [0, 2, 4, 6, 8]
//2: (5) [0, 2, 5, 7, 8]
参考文档：
https://juejin.im/post/5de7c053518825125d1497e2
https://juejin.im/post/5a32688b5188254dd9366d6a
不使用递归的生成路径方法：https://juejin.im/entry/5d849fb45188255a8b635058
网友评论