JavaScript 版数据结构与算法(八)图

今天,我们要讲的是数据结构与算法中的图。

图简介

图是什么?图是网络结构的抽象模型。图是一组由连接的节点(或顶点)。图有啥用?图的作用有这些:

  • 图可以表示任何二元关系,比如道路、航班、通信状态。
  • 非加权图可以用广度优先遍历来计算最短路径。

图的应用非常广泛,远远不止上面这些,有兴趣的同学可以自行去了解更多的图的用途,这里不再详述。

用 JavaScript 编写图类

图的展现方式有很多,常见的包括:

  • 邻接矩阵:矩阵的行列都是图的顶点,数字代表是否连接
  • 邻接表: 由图中每个顶点的相邻顶点列表所组成。存在好几种方式来表示这种数据结构。我们可以用列表(数组)、链表,甚至是散列表或是字典来表示相邻顶点列表。
  • 关联矩阵: 矩阵的行表示顶点,列表示边,数字代表是否连接。

本文将会使用邻接表来展现图。下面就让我们用 JavaScript 来编写图类吧!

私有变量

既然使用 邻接表 来展现图,那么私有变量就是一个数组 vertices 来表示图的所有顶点,还有一个字典 adjList 来表示每个顶点以及它相邻顶点列表。

1
2
var vertices = [];
var adjList = new Dictionary();

实现 addVertex 、addEdge 和 getAdjList 方法

实现 addVertex 方法(添加顶点)、addEdge 方法(添加边)和 getAdjList 方法(获取顶点和相邻顶点组成的字典,即 adjList),可以跑通如下测试:

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
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');
expect(graph.getAdjList()).toEqual({
'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']
});

我们来分析下需求,addVertex 方法其实就是向私有变量 vertices 中 push 新的值,不过也需要在 adjList 中添加新的键,所以实现代码如下:

1
2
3
4
this.addVertex = function (v) {
vertices.push(v);
adjList.set(v, []);
};

addEdge 方法其实就是向私有变量 adjList 中相关的顶点赋值:

1
2
3
4
this.addEdge = function (v, w) {
adjList.get(v).push(w);
adjList.get(w).push(v);
};

getAdjList 方法更简单,直接返回私有变量 adjList.getItems() 即可:

1
2
3
this.getAdjList = function () {
return adjList.getItems();
};

实现广度优先遍历

什么是广度优先遍历?简单来说就是先广后深来遍历图中的顶点。比如一个这样的图:

那么如何实现广度优先遍历呢?这需要用到队列。实现思路如下:

  • 把一个顶点的相邻顶点入队,然后访问该顶点(也可以先访问再入队)
  • 出队重复第一步

比如,访问 A 时,把 BCD 入队,然后接下来就可以最先访问到 BCD 了,不过注意:因为 B 的相邻顶点也包括 A 所以在入队前,需要判断相邻顶点是否入队(或访问过)。为此,我们需要设置两种状态来记录:

  • 白色:没入队
  • 黑色:入队了

所以,我们只需要在不同阶段设置不同颜色,并根据颜色选择性入队即可。实现代码如下:

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
// 将所有顶点初始化为白色
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); // 入队了就设置为黑色
color[v] = 'black';
while (!queue.isEmpty()) {
var u = queue.dequeue(), // 出队重复第一步
neighbors = adjList.get(u);
for (var i = 0; i < neighbors.length; i++) { // 将所有相邻顶点入队
var w = neighbors[i];
if (color[w] === 'white') {
queue.enqueue(w);
color[w] = 'black'; // 入队了就设置为黑色
}
}
if (callback) {
callback(u); // 入队完了相邻顶点,就访问该顶点
}
}
};

实现深度优先遍历

什么是深度优先遍历?简单来说,深度优先遍历就是先深后广来遍历。如图:

那么如何实现深度优先遍历?这需要用到递归。实现思路如下:

  • 先访问一个顶点,然后对相邻顶点挨个进行深度优先遍历。

为了记录访问过的节点,我们用黑色来代表访问过。实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
this.dfs = function (v, callback) {
var color = initializeColor();
dfsVisit(v, color, callback);
};
var dfsVisit = function (u, color, callback) {
if (callback) {
callback(u);
}
var neighbors = adjList.get(u);
color[u] = 'black';
for (var i = 0; i < neighbors.length; i++) {
var w = neighbors[i];
if (color[w] === 'white') {
dfsVisit(w, color, callback);
}
}
};

以上就是广度优先遍历和深度优先遍历的 JavaScript 实现。

教程示例代码及目录

示例代码:https://github.com/lewis617/javascript-datastructures-algorithms

目录:http://www.liuyiqi.cn/tags/数据结构与算法/