8.Javascript图

Javascript数据结构与算法 评论

8-图（第11章）

8.1 图的定义

图是一种非线性结构，由一系列顶点及其连接顶点的边组成。比如A和B、A和D是相邻的，而A和E不是相邻的。一个顶点相邻顶点的数量叫作度，比如A的度为3、D的度为4。路径指相邻顶点的一个连续序列，如ABEI、ACDG；简单路径指不包含重复顶点的路径（除环外），如ADG；环指首尾顶点相同的路径，如ADCA，环也属于简单路径。如果图中每两个顶点之间都有路径相连，则称该图是连通的。

图

如果图中的边具有方向，则成为有向图。如果图中的边是双向的，则称图是强连通的。比如下图中的C和D是强连通的

有向图

8.2 图的表示

8.2.1 顶点

创建图类的第一步就是要创建一个 Vertex 类来保存顶点和边，Vertex 类有两个数据成员：一个用于标识顶点，另一个是表明这个顶点是否被访问过的布尔值 。实现这个类的程序如下：

1
2
3
4
5
6
class Vertex {
  constructor(label, color) {
    this.label = label
    this.color = color
  }
}

（原书上关于顶点的实现跟我上面的程序还不一样。其实顶点不需要用程序实现的，接下来也用不到）

8.2.2 边

图的实际信息都保存在边上面，因为它们描述了图的结构。表示图的方法有好几种，我们选用最常见的邻接表法表示边。这种方法将边存储为由顶点的相邻顶点列表构成的数组，并以此顶点作为索引。使用这种方案，当我们在程序中引用一个顶点时，可以高效地访问与这个顶点相连的所有顶点的列表。比如，如果顶点 2 与顶点 0、1、 3、 4 相连，我们就可以在map键值为2的位置，存储它的相邻顶点0、1、3、4

8.2.3 图

程序如下：这个类会记录一个图表示了多少条边，并使用数组来记录顶点数。使用一个键值为数组的hash表来存储顶点的相邻顶点

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
class Graph {
  constructor() {
    // 顶点数量
    this.vertices = []
    // 邻接表
    this.adj = new Map()
  }
  // 添加顶点
  addVertice(v) {
    this.vertices.push(v)
    this.adj.set(v, [])
  }
  // 添加边
  addEdge(v, w) {
    // console.log('this.adj.get(v):', this.adj.get(v))
    // console.log('this.adj.get(w):', this.adj.get(w))
    this.adj.get(v).push(w)
    this.adj.get(w).push(v)
  }
  // 显示这个图
  showGraph() {
    let keys = this.adj.keys()
    for (let k of keys) {
      console.log(k + '->')
      for (let i of this.adj.get(k)) {
        console.log(i + ' ')
      }
    }
  }
}

测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
let g = new Graph()
let vertices = [1, 2, 3, 4, 5, 6, 7]

vertices.forEach(v => {
  g.addVertice(v)
})

g.addEdge(1, 2)
g.addEdge(1, 3)
g.addEdge(1, 6)
g.addEdge(2, 7)
g.addEdge(3, 5)
g.addEdge(3, 4)
g.addEdge(3, 6)
g.showGraph()
// 打印结果
1-> 2 3 6
2-> 1 7 
3-> 1 5 4 6
4-> 3
5-> 3
6-> 1 3 
7-> 2

打印结果正确，说明我的程序没有问题。

8.3 图的遍历

图的遍历有两种常用的方法：深度优先搜索和广度优先搜索。

8.3.1 深度优先搜索

深度优先搜索包括从一条路径的起始顶点开始追溯，直到到达最后一个顶点，然后回溯，继续追溯下一条路径，直到到达最后的顶点，如此往复，直到没有路径为止。

深度优先搜索

深度优先搜索算法比较简单：访问一个没有访问过的顶点，将它标记为已访问，再递归地去访问在初始顶点的邻接表中其他没有访问过的顶点。

8.3.2 广度优先遍历

广度优先搜索从第一个顶点开始，尝试访问尽可能靠近它的顶点。本质上，这种搜索在图上是逐层移动的，首先检查最靠近第一个顶点的层，再逐渐向下移动到离起始顶点最远的层。

广度优先遍历

8.4 程序实现

假设我们有以下一个图，我们尝试下实现这个图，并且分别用深度遍历和广度遍历访问这个图

案例

原书中对图的实现太粗糙了，原书中图要求每个顶点都是数字，我这边做了一下优化

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
// 图
class Graph {
  constructor() {
    // 顶点数量
    this.vertices = []
    // 邻接表
    this.adj = new Map()
  }
  // 添加顶点
  addVertice(v) {
    this.vertices.push(v)
    this.adj.set(v, [])
  }
  // 添加边
  addEdge(v, w) {
    // console.log('this.adj.get(v):', this.adj.get(v))
    // console.log('this.adj.get(w):', this.adj.get(w))
    this.adj.get(v).push(w)
    this.adj.get(w).push(v)
  }
  // 显示这个图
  showGraph() {
    let keys = this.adj.keys()
    for (let k of keys) {
      console.log(k + '->')
      for (let i of this.adj.get(k)) {
        console.log(i + ' ')
      }
    }
  }
  // 搜索辅助函数，对对顶点进行初始化，顶点没有被访问过就是白色，顶点被访问过但是还没探索的话是灰色，顶点被探索过就是黑色
  initialColor() {
    let color = new Map()
    this.vertices.forEach(ele => {
      color.set(ele, 'white')
    })
    return color
  }

  // 深度遍历所有顶点
  dfs(callback) {
    let color = this.initialColor()
    this.vertices.forEach(node => {
      if (color.get(node) === 'white') {
        this.dfsVisit(node, color, callback)
      }
    })
  }
  // 递归遍历顶点的邻接表
  dfsVisit(node, color, callback) {
    let neighbors = this.adj.get(node)
    color.set(node, 'grey')
    if (callback) {
      callback(node)
    }
    neighbors.forEach(neighNode => {
      if (color.get(neighNode) === 'white') {
        this.dfsVisit(neighNode, color, callback)
      }
    })
    color.set(node, 'black')
  }
  // 广度遍历所有顶点
  bfs(callback) {
    let color = this.initialColor()
    let queue = []
    if (this.vertices[0]) {
      queue.push(this.vertices[0])
    }
    while (queue.length > 0) {
      let qNode = queue.shift()
      let neighbors = this.adj.get(qNode)
      color.set(qNode, 'grey')
      neighbors.forEach(ele => {
        if (color.get(ele) === 'white') {
          color.set(ele, 'grey')
          queue.push(ele)
        }
      })
      color.set(qNode, 'black')
      if (callback) {
        callback(qNode)
      }
    }
  }
}

上面的程序实现图的定义，还实现了深度遍历和广度遍历的方法。我们队程序测试下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
let g = new Graph()
let vertices = [1, 2, 3, 4, 5, 6, 7]
vertices.forEach(v => {
  g.addVertice(v)
})
g.addEdge(1, 2)
g.addEdge(1, 3)
g.addEdge(1, 6)
g.addEdge(2, 7)
g.addEdge(3, 5)
g.addEdge(3, 4)
g.addEdge(3, 6)

// 深度遍历
g.dfs(v=>console.log(v)) // 1 2 7 3 5 4 6
// 广度遍历
g.bfs(v=>console.log(v)) // 1 2 3 6 7 5 4

测试结果是正确的，说明我们的程序实现没有问题

8.5 查找最短路径

图的最常见的操作是查找从一个顶点到另一个顶点的最短路径，就要用到广度搜索。要查找从顶点 A 到顶点 D 的最短路径，我们首先会查找从 A 到 D 是否有任何一条单边路径，接着查找两条边的路径，以此类推。这正是广度优先搜索的搜索过程，因此我们可以轻松地修改广度优先搜索算法，找出最短路径。

代码如下：

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
// 获取每一个点到顶点的距离和其上一个顶点
bfsDistance() {
  let color = this.initialColor()
  let queue = []
  let distance = new Map()
  let pred = new Map()
  if (this.vertices[0]) {
    queue.push(this.vertices[0])
  }
  this.vertices.forEach(ele => {
    distance.set(ele, 0)
    pred.set(ele, null)
  });
  while (queue.length > 0) {
    let qNode = queue.shift()
    let neighbors = this.adj.get(qNode)
    color.set(qNode, 'grey')
    neighbors.forEach(ele => {
      if (color.get(ele) === 'white') {
        color.set(ele, 'grey')
        queue.push(ele)
        distance.set(ele, distance.get(qNode) + 1)
        pred.set(ele, qNode)
      }
    })
    color.set(qNode, 'black')
  }
  return {
    distance: distance,
    pred: pred
  }
}
// 获取每一个点到顶点的路径
getBfsPath() {
  if (this.vertices.length > 0) {
    let shortestPath = this.bfsDistance()
    let fromVertex = this.vertices[0]
    let paths = []
    for (let i = 0; i < this.vertices.length; i++) {
      let path = []
      let toVertex = this.vertices[i]
      for (let v = toVertex; v !== fromVertex; v = shortestPath.pred.get(v)) {
        path.push(v)
      }
      path.push(fromVertex)
      paths.push(path)
    }
    return paths
  }
}
// 获取到顶点的最短路径
getShortestPath(v) {
  let path = null
  let paths = this.getBfsPath()
  for (let i = 0; i < paths.length; i++) {
    if (paths[i][0] === v) {
      path = paths[i]
      break
    }
  }
  return path
}

测试：

我们以获取顶点到第4个点的最短路径为例，测试如下

1
2
g.getShortestPath(g.vertices[4])
// [5,3,1]

案例获取顶点到某个点的最短路径，怎么样获取非顶点的两个点之间的最短路径呢？ 其实道理很简单，你换下顶点就可以了。在图里，并没有规定那个必须是顶点。

8.6 拓扑排序

拓扑排序会对有向图的所有顶点进行排序，使有向图从前面的顶点指向后面的顶点。如下图是计算机学科的有向图模型。

有向图

这个图的拓扑排序结果将会是以下序列：

  1. CS1
  2. CS2
  3. 汇编语言
  4. 数据结构
  5. 操作系统
  6. 算法

课程3和课程4可以同时上，课程5和课程6也可以同时上，但是其他课程就要有优先级了。比如c1一定要在cs2之前上。

拓扑排序代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 拓扑排序
topSort() {
  let stack = []
  let color = this.initialColor()
  this.vertices.forEach(ele => {
    if (color.get(ele) === 'white') {
      this.topSortVisit(ele, stack, color)
    }
  })
  console.log('stack:', stack)
}
topSortVisit(ele, stack, color) {

  color.set(ele, 'grey')
  stack.push(ele)
  let neighbors = this.adj.get(ele)
  neighbors.forEach(nNode => {
    if (color.get(nNode) === 'white') {
      this.topSortVisit(nNode, stack, color)
    }
  })
}

用已有的案例测试:

1
2
g.topSort()
// stack: (7) [1, 2, 7, 3, 5, 4, 6]

用其他案例测试下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let g = new Graph()
let vertices = ['cs1', 'cs2', '汇编语言', '数据结构', '操作系统', '算法']

vertices.forEach(v => {
  g.addVertice(v)
})

g.addEdge('cs1', 'cs2')
g.addEdge('cs2', '汇编语言')
g.addEdge('cs2', '数据结构')
g.addEdge('数据结构', '操作系统')
g.addEdge('数据结构', '算法')
g.topSort()
// stack: (6) ["cs1", "cs2", "汇编语言", "数据结构", "操作系统", "算法"]

测试应该是没问题的。

本章节完整代码如下：

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
// 图
class Graph {
  constructor() {
    // 顶点数量
    this.vertices = []
    // 邻接表
    this.adj = new Map()
  }
  // 添加顶点
  addVertice(v) {
    this.vertices.push(v)
    this.adj.set(v, [])
  }
  // 添加边
  addEdge(v, w) {
    // console.log('this.adj.get(v):', this.adj.get(v))
    // console.log('this.adj.get(w):', this.adj.get(w))
    this.adj.get(v).push(w)
    this.adj.get(w).push(v)
  }
  // 显示这个图
  showGraph() {
    let keys = this.adj.keys()
    for (let k of keys) {
      console.log(k + '->')
      for (let i of this.adj.get(k)) {
        console.log(i + ' ')
      }
    }
  }
  // 搜索辅助函数，对对顶点进行初始化，顶点没有被访问过就是白色，顶点被访问过但是还没探索的话是灰色，顶点被探索过就是黑色
  initialColor() {
    let color = new Map()
    this.vertices.forEach(ele => {
      color.set(ele, 'white')
    })
    return color
  }

  // 深度遍历所有顶点
  dfs(callback) {
    let color = this.initialColor()
    this.vertices.forEach(node => {
      if (color.get(node) === 'white') {
        this.dfsVisit(node, color, callback)
      }
    })
  }
  // 递归遍历顶点的邻接表
  dfsVisit(node, color, callback) {
    let neighbors = this.adj.get(node)
    color.set(node, 'grey')
    if (callback) {
      callback(node)
    }
    neighbors.forEach(neighNode => {
      if (color.get(neighNode) === 'white') {
        this.dfsVisit(neighNode, color, callback)
      }
    })
    color.set(node, 'black')
  }
  // 广度遍历所有顶点
  bfs(callback) {
    let color = this.initialColor()
    let queue = []
    if (this.vertices[0]) {
      queue.push(this.vertices[0])
    }
    while (queue.length > 0) {
      let qNode = queue.shift()
      let neighbors = this.adj.get(qNode)
      color.set(qNode, 'grey')
      neighbors.forEach(ele => {
        if (color.get(ele) === 'white') {
          color.set(ele, 'grey')
          queue.push(ele)
        }
      })
      color.set(qNode, 'black')
      if (callback) {
        callback(qNode)
      }
    }
  }
  // 获取每一个点到顶点的距离和其上一个顶点
  bfsDistance() {
    let color = this.initialColor()
    let queue = []
    let distance = new Map()
    let pred = new Map()
    if (this.vertices[0]) {
      queue.push(this.vertices[0])
    }
    this.vertices.forEach(ele => {
      distance.set(ele, 0)
      pred.set(ele, null)
    });
    while (queue.length > 0) {
      let qNode = queue.shift()
      let neighbors = this.adj.get(qNode)
      color.set(qNode, 'grey')
      neighbors.forEach(ele => {
        if (color.get(ele) === 'white') {
          color.set(ele, 'grey')
          queue.push(ele)
          distance.set(ele, distance.get(qNode) + 1)
          pred.set(ele, qNode)
        }
      })
      color.set(qNode, 'black')
    }
    return {
      distance: distance,
      pred: pred
    }
  }
  // 获取每一个点到顶点的路径
  getBfsPath() {
    if (this.vertices.length > 0) {
      let shortestPath = this.bfsDistance()
      let fromVertex = this.vertices[0]
      let paths = []
      for (let i = 0; i < this.vertices.length; i++) {
        let path = []
        let toVertex = this.vertices[i]
        for (let v = toVertex; v !== fromVertex; v = shortestPath.pred.get(v)) {
          path.push(v)
        }
        path.push(fromVertex)
        paths.push(path)
      }
      return paths
    }
  }
  // 获取到顶点的最短路径
  getShortestPath(v) {
    let path = null
    let paths = this.getBfsPath()
    for (let i = 0; i < paths.length; i++) {
      if (paths[i][0] === v) {
        path = paths[i]
        break
      }
    }
    return path
  }
  // 拓扑排序
  topSort() {
    let stack = []
    let color = this.initialColor()
    this.vertices.forEach(ele => {
      if (color.get(ele) === 'white') {
        this.topSortVisit(ele, stack, color)
      }
    })
    console.log('stack:', stack)
  }
  topSortVisit(ele, stack, color) {

    color.set(ele, 'grey')
    stack.push(ele)
    let neighbors = this.adj.get(ele)
    neighbors.forEach(nNode => {
      if (color.get(nNode) === 'white') {
        this.topSortVisit(nNode, stack, color)
      }
    })
  }
}

let g = new Graph()
let vertices = [1, 2, 3, 4, 5, 6, 7]

vertices.forEach(v => {
  g.addVertice(v)
})

g.addEdge(1, 2)
g.addEdge(1, 3)
g.addEdge(1, 6)
g.addEdge(2, 7)
g.addEdge(3, 5)
g.addEdge(3, 4)
g.addEdge(3, 6)
g.getBfsPath()

个人评价：关于图的知识常用的大概就这么多，书上有关图的代码写的真是一团糟，很多要自己查资料实现。这作者真是太不负责任了

锅锅复锅锅

中国贫困人口，特别需要关爱人群，微信guo330504。