javaScript的数据结构与算法（六）——图
Opened this issue · 4 comments
1、 图
图是网络结构的抽象模型。图是一组由边连接的节点，任何二元关系都可以用图来表示。
1.1、图的相关概念
一个图G = （V，E）由以下元素组成。
- V：一组顶点
- E：一组边，连接V中的顶点
下图表示一个图：
由一条边连接在一起的顶点称为相邻顶点。比如上图的A和B是相邻的，A和D是相邻的，A和C是相邻的，A和E不是相邻的。一个顶点的度是其相邻顶点的数量。比如，A和其他三个顶点相连接，因此，A的度为3；E和其他两个顶点相连，因此E的度为2。路径是顶点v1，v2，...，vk的一个连续序列，其中v[i]和v[i+1]是相邻的。以上的图为例，其中的路径有ABEI和ACDG。
1.2、图的表示
图最常见的实现是邻接矩阵。每个节点都和一个整数相关联，该整数作为数组的索引。这里不作讨论。另一种图的表示方式是一种叫做邻接表的动态数据结构。邻接表由图中每个顶点的相邻顶点列表所组成。我们可以用数组，链表，甚至是散列表或是字典来表示相邻顶点列表。下面的示意图展示了邻接表的数据结构。我们后面也会用代码示例这种数据结构。
示例代码如下：
function Graph() {
var vertices = []; //存储图中所有的顶点名字
var adjList = new Dictionary();//用之前的一个字典来存储邻接表
this.addVertex = function(v){ //添加顶点
vertices.push(v);
adjList.set(v, []); //顶点为键，字典值为空数组
};
this.addEdge = function(v, w){ //添加边
adjList.get(v).push(w); //基于有向图
adjList.get(w).push(v); //基于无向图
};
this.toString = function(){
var s = '';
for (var i=0; i<vertices.length; i++){
s += vertices[i] + ' -> ';
var neighbors = adjList.get(vertices[i]);
for (var j=0; j<neighbors.length; j++){
s += neighbors[j] + ' ';
}
s += '\n';
}
return s;
};
var initializeColor = function(){
var color = [];
for (var i=0; i<vertices.length; i++){
color[vertices[i]] = 'white';
}
return color;
};
}
//测试
var graph = new Graph();
var myVertices = ['A','B','C','D','E','F','G','H','I'];
for (var i=0; i<myVertices.length; i++){
graph.addVertex(myVertices[i]);
}
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');
console.log(graph.toString());
结果如下：
A -> B C D
B -> A E F
C -> A D G
D -> A C G H
E -> B I
F -> B
G -> C D
H -> D
I -> E
1.3、图的遍历
和树的数据结构类似，我们可以访问图的所有节点。有两种算法可以对图进行遍历：广度优先搜索（Breadth-First Search，BFS）和深度优先搜索（Depth-First Search，DFS）。图遍历可以用来寻找特定的顶点或寻找两个顶点之间的路径，检查图是否连通，检查图是否含有环等。
图遍历算法的**是必须追踪每个第一次访问的节点，并且追踪有哪些节点还没有被完全探索。对于两种图遍历算法，都需要明确指出第一个被访问的顶点。完全探索一个顶点要求我们查看该顶点的每一条边。对应每一条边所连接的没有被访问过的顶点，将其标注为被发现的，并将其加进待访问顶点列表中。
为了保证算法的效率，务必访问每个顶点至多两次。连通图中每条边和顶点都会被访问到。当要标注已经访问过的顶点时，我们用三种颜色来反映它们的状态：
- 白色：表示该顶点还没有被访问。
- 灰色：表示该顶点被访问过，但并未被探索过。
- 黑色：表示该顶点被访问过且被完全搜索过。
1.3.1、广度优先搜索（BFS）
广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访问图的一层。换句话说，就是先宽后深的访问顶点。以下是从顶点v开始的广度优先搜索算法所遵循的步骤。
- （1）创建一个队列Q。
- （2）将v标注为被发现的（灰色），并将v入队列Q。
- （3）如果Q非空，则运行以下步骤：
（a）将u从Q中出队列；
（b）将标注u为被发现的（灰色）；
（c）将u所有未被访问过的邻点（白色）入队列；
（d）将u标注为已被探索的（黑色）；
示例代码如下：
var initializeColor = function(){
var color = [];
for (var i=0; i<vertices.length; i++){
color[vertices[i]] = 'white'; //初始化所有的顶点都是白色
}
return color;
};
this.bfs = function(v, callback){
var color = initializeColor(),
queue = new Queue(); //创建一个队列
queue.enqueue(v); //入队列
while (!queue.isEmpty()){
var u = queue.dequeue(), //出队列
neighbors = adjList.get(u); //邻接表
color[u] = 'grey'; //发现了但还未完成对其的搜素
for (var i=0; i<neighbors.length; i++){
var w = neighbors[i]; //顶点名
if (color[w] === 'white'){
color[w] = 'grey'; //发现了它
queue.enqueue(w); //入队列循环
}
}
color[u] = 'black'; //已搜索过
if (callback) {
callback(u);
}
}
};
//测试如下：
function printNode(value){
console.log('Visited vertex: ' + value);
}
graph.bfs(myVertices[0], printNode);
结果如下：
Visited vertex: A
Visited vertex: B
Visited vertex: C
Visited vertex: D
Visited vertex: E
Visited vertex: F
Visited vertex: G
Visited vertex: H
Visited vertex: I
1.3.2、深度优先搜索（BFS）
深度优先搜索算法将会是从第一个指定的顶点开始遍历图，沿着路径直到这条路径最后一个顶点被访问了，接着原路回退并探索下一条路径。换句话说，它是先深度后广度地访问顶点。深度优先搜索算法不需要一个源顶点。要访问顶点v，照如下的步骤做：
- （1）标注v为被发现的（灰色）。
- （2）对应v的所有未访问的邻点w。
（a）访问顶点w。 - （3）标注v为已被探索的（黑色）。
如你所见，深度优先搜索的步骤是递归的，这意味着深度优先搜索算法使用栈来存储函数调用（由递归调用所创建的栈）。示例代码如下：
this.dfs = function(callback){
var color = initializeColor(); //前面的颜色数组
for (var i=0; i<vertices.length; i++){
if (color[vertices[i]] === 'white'){
dfsVisit(vertices[i], color, callback); //递归调用未被访问过的顶点
}
}
};
var dfsVisit = function(u, color, callback){
color[u] = 'grey';
if (callback) {
callback(u);
}
var neighbors = adjList.get(u); //邻接表
for (var i=0; i<neighbors.length; i++){
var w = neighbors[i];
if (color[w] === 'white'){
dfsVisit(w, color, callback); //添加顶点w入栈
}
}
color[u] = 'black';
};
//测试如下：
function printNode(value){
console.log('Visited vertex: ' + value);
}
graph.dfs(printNode);
结果如下：
Visited vertex: A
Visited vertex: B
Visited vertex: E
Visited vertex: I
Visited vertex: F
Visited vertex: C
Visited vertex: D
Visited vertex: G
Visited vertex: H
动态规划背包算法呢
看了这篇文章感觉比我买的书好很多，但是有个地方不理解，callback 这不是回调函数么，您说的是需要使用递归，递归与回调 我看不懂
@pengliheng 动态规划和图这种数据结构没啥关系