数据结构之图

图(Graph)结构是一种非线性的数据结构,图在实际生活中有很多例子,比如交通运输网,地铁网络,社交网络,计算机中的状态执行(自动机)等等都可以抽象成图结构。图结构比树结构复杂的非线性结构。

图的结构

图

一个图G=(V, E)由以下元素组成:

  • 顶点(vertex,V):图中的数据元素
  • 边(edge,E):图中连接这些顶点的线

所有的顶点构成一个顶点集合,所有的边构成边的集合,一个完整的图结构就是由顶点集合和边集合组成。

由一条边连接在一起的顶点称谓相邻顶点,一个顶点的是其相邻顶点的数量。

有向图/无向图

无向图

图

如果一个图结构中,所有的边都没有方向性,那么这种图便称为无向图。典型的无向图,如图所示。由于无向图中的边没有方向性,这样我们在表示边的时候对两个顶点的顺序没有要求。例如顶点VI和顶点V2之间的边,可以表示为(V1, V2),也可以表示为(V2,V1)。

有向图

图

一个图结构中,边是有方向性的,那么这种图就称为有向图,如图三所示。由于图的边有方向性,我们在表示边的时候对两个顶点的顺序就有要求。我们采用尖括号表示有向边,例如<V1,V2>表示从顶点V1到顶点V2,而<V4,V1>表示顶点V4到顶点V1。

图的表示

理论上,图就是一堆顶点和边对象而已,但是怎么在代码中来描述呢?

有两种主要的方法:邻接列表邻接矩阵

邻接列表

在邻接列表实现中,每一个顶点会存储一个从它这里开始的边的列表。比如,如果顶点A 有一条边到B、C和D,那么A的列表中会有3条边。

图

邻接矩阵

在邻接矩阵实现中,由行和列都表示顶点,由两个顶点所决定的矩阵对应元素表示这里两个顶点是否相连。

图

代码实现

以邻接列表为例,我们实现一个图类。使用一个数组来存储图中所有的顶点的名字,以及一个字典来存储邻结表,字典使用顶点的名称作为键,邻接顶点列表作为值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function Graph() {
var vertices = [];
var adjList = {};

this.addVertex = function(v) {
vertices.push(v);
adjList[v] = [];
}

this.addEdge = function(v, w) {
adjList[v].push(w);
adjList[w].push(v);
}
}

图的遍历

有两种算法可以对图进行遍历:广度优先搜索(Breadth-First Search, BFS)深度优先搜索(Depth-First Search, DFS)

图遍历算法的思想是追踪每个第一次访问的节点,并且追踪有哪些节点还没有被完全探索。对于两种图遍历算法,都需要明确指出第一个被访问的节点。完全探索一个顶点要求我们查看该顶点的每一条边,对于每一条边所连接的没有被访问过的顶点,将其标注为被发现状态,并将其加进待访问顶点列表中。

为了保证算法的效率,每个顶点最多访问两次。

广度优先搜索

图

广度优先搜索类似于树的层次遍历。从图的某一顶点出发,遍历每一个顶点时,依次遍历其所有的邻接点,然后再从这些邻接点出发,同样依次访问它们的邻接点。按照此过程,直到图中所有被访问过的顶点的邻接点都被访问到。

最后还需要做的操作就是查看图中是否存在尚未被访问的顶点,若有,则以该顶点为起始点,重复上述遍历的过程。

以上无向图为例,假设 V1 作为起始点,遍历其所有的邻接点 V2 和 V3 ,以 V2 为起始点,访问邻接点 V4 和 V5 ,以 V3 为起始点,访问邻接点 V6 、 V7 ,以 V4 为起始点访问 V8 ,以 V5 为起始点,由于 V5 所有的起始点已经全部被访问,所有直接略过, V6 和 V7 也是如此。

V1 -> V2 -> v3 -> V4 -> V5 -> V6 -> V7 -> V8

代码实现:

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
// 初始化所有顶点,标记为未被访问状态
this.initFlags = function() {
var flags = [];
for(var i = 0; i < vertices.length; i++) {
flags[vertices[i]] = 0;
}
return flags;
}

this.bfs = function(v) {
var flags = initFlags(), queue = new Queue();
// 将未访问顶点压入栈
queue.enqueue(v);

while(!queue.isEmpty()) {
var u = queue.dequeue();
var neighbors = adjList[u];
// 将顶点标记为已访问但未探索
flags[u] = 1;
for (var i = 0; i < neighbors.length; i++) {
var w = neighbors[i];
if (flags[w] == 0) {
flags[w] = 1;
queue.enqueue(w);
}
}
// 将顶点标记为已访问且完成探索
flags[u] = 2;
}
}

深度优先搜索

深度优先搜索算法将会从第一个指定的顶点开始遍历图。沿着路径直到这条路径最后一个顶点被访问,接着原图回退并探索下一条路径。它是先深度后广度地访问顶点。

图

深度优先搜索的过程类似于树的先序遍历,例如上图是一个无向图,采用深度优先算法遍历这个图的过程为:

  1. 首先任意找一个未被遍历过的顶点,例如从 V1 开始,由于 V1 率先访问过了,所以,需要标记 V1 的状态为访问过;
  2. 然后遍历 V1 的邻接点,例如访问 V2 ,并做标记,然后访问 V2 的邻接点,例如 V4 (做标记),然后 V8 ,然后 V5;
  3. 当继续遍历 V5 的邻接点时,根据之前做的标记显示,所有邻接点都被访问过了。此时,从 V5 回退到 V8 ,看 V8 是否有未被访问过的邻接点,如果没有,继续回退到 V4 , V2 , V1 ;
  4. 通过查看 V1 ,找到一个未被访问过的顶点 V3 ,继续遍历,然后访问 V3 邻接点 V6 ,然后 V7 ;
  5. 由于 V7 没有未被访问的邻接点,所有回退到 V6 ,继续回退至 V3 ,最后到达 V1 ,发现没有未被访问的;
  6. 最后一步需要判断是否所有顶点都被访问,如果还有没被访问的,以未被访问的顶点为第一个顶点,继续依照上边的方式进行遍历。

根据上边的过程,可以得到上图通过深度优先搜索获得的顶点的遍历次序为:

V1 -> V2 -> V4 -> V8 -> V5 -> V3 -> V6 -> V7。

代码实现:

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
this.initFlags = function() {
var flags = [];
for(var i = 0; i < vertices.length; i++) {
flags[vertices[i]] = 0;
}
return flags;
}

this.dfs = function() {
var flags = this.initFlags();
for (var i = 0; i < vertices.length; i++) {
if (flags[vertices[i]] == 0) {
this.dfsvisit(vertices[i], flags);
}
}
}

this.dfsvisit = function(u, flags) {
flags[u] = 1;
console.log(u);
var neighbors = adjList[u];
for (var i = 0; i < neighbors.length; i++) {
var w = neighbors[i];
if (flags[w] == 0) {
this.dfsvisit(w, flags);
}
}
flags[u] = 2;
}

全部代码

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
/ 队列
function Queue() {

let items = [];

this.enqueue = function(element) {
items.push(element);
}

this.dequeue = function() {
return items.shift();
}

this.front = function() {
return items[0];
}

this.isEmpty = function() {
return items.length == 0;
}

this.toString = function() {
return items.toString();
}
}

// 图
function Graph() {
var vertices = [];
var adjList = {};

this.addVertex = function(v) {
vertices.push(v);
adjList[v] = [];
}

this.addEdge = function(v, w) {
adjList[v].push(w);
adjList[w].push(v);
}

this.initFlags = function() {
var flags = [];
for(var i = 0; i < vertices.length; i++) {
flags[vertices[i]] = 0;
}
return flags;
}

this.bfs = function(v) {
var flags = this.initFlags(), queue = new Queue();
queue.enqueue(v);

while(!queue.isEmpty()) {
var u = queue.dequeue();
var neighbors = adjList[u];
flags[u] = 1;
for (var i = 0; i < neighbors.length; i++) {
var w = neighbors[i];
if (flags[w] == 0) {
flags[w] = 1;
queue.enqueue(w);
}
}
console.log(u);
flags[u] = 2;
}
}

this.dfs = function() {
var flags = this.initFlags();
for (var i = 0; i < vertices.length; i++) {
if (flags[vertices[i]] == 0) {
this.dfsvisit(vertices[i], flags);
}
}
}

this.dfsvisit = function(u, flags) {
flags[u] = 1;
console.log(u);
var neighbors = adjList[u];
for (var i = 0; i < neighbors.length; i++) {
var w = neighbors[i];
if (flags[w] == 0) {
this.dfsvisit(w, flags);
}
}
flags[u] = 2;
}

this.toString = function() {
var s = '';
for(var i = 0; i < vertices.length; i++) {
s += vertices[i] + ' -> ';
var neighbors = adjList[vertices[i]];
for (var j = 0; j < neighbors.length; j++) {
s += neighbors[j] + ' ';
}
s += '\n';
}
return s;
}
}
有用就打赏一下作者吧!