资讯专栏INFORMATION COLUMN

【你该懂一点Javascript算法系列】之【图类】的定义及深度优先与广度优先搜索算法

qqlcbb / 1355人阅读

摘要:邻接矩阵在邻接矩阵实现中,由行和列都表示顶点,由两个顶点所决定的矩阵对应元素表示这里两个顶点是否相连如果相连这个值表示的是相连边的权重。直到返回到顶点完成探索具体还有版的深度和广度优先的算法,具体代码奉上直达地址


github直达地址 https://github.com/fanshyiis/...

在计算机科学中,一个图就是一些顶点的集合,这些顶点通过一系列边结对(连接)。顶点用圆圈表示,边就是这些圆圈之间的连线。顶点之间通过边连接。

</>复制代码

  1. 注意:顶点有时也称为节点或者交点,边有时也称为链接。

一个图可以表示一个社交网络,每一个人就是一个顶点,互相认识的人之间通过边联系。

理论上,图就是一堆顶点和边对象而已,但是怎么在代码中来描述呢?
有两种主要的方法:邻接列表和邻接矩阵。

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

邻接列表只描述了指向外部的边。A 有一条边到B,但是B没有边到A,所以 A没有出现在B的邻接列表中。查找两个顶点之间的边或者权重会比较费时,因为遍历邻接列表直到找到为止。

邻接矩阵:在邻接矩阵实现中,由行和列都表示顶点,由两个顶点所决定的矩阵对应元素表示这里两个顶点是否相连、如果相连这个值表示的是相连边的权重。例如,如果从顶点A到顶点B有一条权重为 5.6 的边,那么矩阵中第A行第B列的位置的元素值应该是5.6:

往这个图中添加顶点的成本非常昂贵,因为新的矩阵结果必须重新按照新的行/列创建,然后将已有的数据复制到新的矩阵中。
所以使用哪一个呢?大多数时候,选择邻接列表是正确的。下面是两种实现方法更详细的比较。
假设 V 表示图中顶点的个数,E 表示边的个数。

“检查相邻性” 是指对于给定的顶点,尝试确定它是否是另一个顶点的邻居。在邻接列表中检查相邻性的时间复杂度是O(V),因为最坏的情况是一个顶点与每一个顶点都相连。
在 稀疏图的情况下,每一个顶点都只会和少数几个顶点相连,这种情况下相邻列表是最佳选择。如果这个图比较密集,每一个顶点都和大多数其他顶点相连,那么相邻矩阵更合适。

了解了图的基本定义后我们来看下如何用es6的类class思想来实现图类

首先我们先定义两个辅助类

</>复制代码

  1. class Dictionary {
  2. constructor () {
  3. this.items = {}
  4. }
  5. has (key) {
  6. return key in this.items
  7. }
  8. set (key, val) {
  9. this.items[key] = val
  10. }
  11. delete (key) {
  12. if (this.has(key)) {
  13. delete this.items[key]
  14. return true
  15. } else {
  16. return false
  17. }
  18. }
  19. get (key) {
  20. return this.has(key)? this.items[key] : undefined
  21. }
  22. values () {
  23. let values = []
  24. for (let k in this.items) {
  25. if (this.has(k)) {
  26. values.push(this.items[k])
  27. }
  28. }
  29. return values
  30. }
  31. }
  32. class Queue {
  33. constructor () {
  34. this.items = []
  35. }
  36. enqueue (element) {
  37. this.items.push(element)
  38. }
  39. dequeue () {
  40. return this.items.shift()
  41. }
  42. isEmpty() {
  43. return this.items.length === 0
  44. }
  45. }

</>复制代码

  1. Dictionary 字典类来辅助存贮键值对
    Queue 队列类来存贮队列

</>复制代码

  1. //定义class Graph
  2. class Graph {
  3. constructor () {
  4. this.vertices = []
  5. this.adjList = new Dictionary()
  6. }
  7. }

</>复制代码

  1. 定义Graph类并且在构造函数里初始化字段
    vertices 存储点信息
    adjList 存储顶点间的链接关系

</>复制代码

  1. addVertex (v) {
  2. this.vertices.push(v)
  3. this.adjList.set(v, [])
  4. }
  5. addEdge (v, w) {
  6. this.adjList.get(v).push(w)
  7. }

</>复制代码

  1. addVertex 添加顶点的方法,存贮在数组vertices,并且初始化adjList字典里的值
    addEdge 添加单向边 接收两个值 在邻接字典里加上从第一个顶点到第二个的关系

到这 一个基本的类就完成了,我们可以通过测试代码来测试

</>复制代码

  1. et graph = new Graph()
  2. let mv = ["A", "B", "C", "D", "E", "F", "G", "H", "I"]
  3. mv.map(val => {
  4. graph.addVertex(val)
  5. })
  6. graph.addEdge("A", "B")
  7. graph.addEdge("A", "C")
  8. graph.addEdge("A", "D")
  9. graph.addEdge("C", "D")
  10. graph.addEdge("C", "G")
  11. graph.addEdge("D", "G")
  12. graph.addEdge("D", "H")
  13. graph.addEdge("B", "E")
  14. graph.addEdge("B", "F")
  15. graph.addEdge("E", "I")

得到的图

下面我们来定义一个功能来打印图

</>复制代码

  1. toString () {
  2. let s = ""
  3. for (let i = 0; i < this.vertices.length; i++) {
  4. s += this.vertices[i] + "->"
  5. let neighbors = this.adjList.get(this.vertices[i])
  6. for (let j = 0; j < neighbors.length; j++) {
  7. s += neighbors[j] + " "
  8. }
  9. s += "
  10. "
  11. }
  12. return s
  13. }

</>复制代码

  1. 执行文件 node graph.js

得到结果

</>复制代码

  1. A->B C D
  2. B->E F
  3. C->D G
  4. D->G H
  5. E->I
  6. F->
  7. G->

好到这就基本完成类的结构了,下面进行图的遍历

</>复制代码

  1. 广度优先 - 数据结构 队列

先上代码

</>复制代码

  1. BFS (v, callback) {
  2. let color = this.initializeColor(),
  3. queue = new Queue()
  4. queue.enqueue(v)
  5. while (!queue.isEmpty()) {
  6. let u = queue.dequeue(),
  7. neighbors = this.adjList.get(u)
  8. color[u] = "grey"
  9. neighbors.map(val => {
  10. if (color[val] === "white") {
  11. color[val] = "grey"
  12. queue.enqueue(val)
  13. }
  14. })
  15. color[u] = "black"
  16. if (callback) {
  17. callback(u)
  18. }
  19. }
  20. }

基本思想如下
1.初始化各个顶点的颜色(白色 - 未访问; 灰色 - 已发现; 黑色 - 已经探索完)
2.初始化一个队列
3.首先队列入顶点 v
4.如果队列不会空,则取队列第一个进行探索
5.探索过程中获取当前顶点的所有邻接顶点,并推进队列
6.完成5后,标记当前为黑色

图示例
A 探索 队列入 B - C - D
完成 A探索
出B 探索B 队列再入 E - F 当前 CDEF
完成 B探索
出C 探索 队列再入 G 当前DEFG
。。。

直到所有顶点探索完

</>复制代码

  1. 深度优先 - 数据结构 栈

先上代码

</>复制代码

  1. DFS (callback) {
  2. let color = this.initializeColor()
  3. this.vertices.map(val => {
  4. if (color[val] === "white") {
  5. this.dfsVisit(val, color, callback)
  6. }
  7. })
  8. }
  9. dfsVisit (u, color, callback) {
  10. color[u] = "grey"
  11. if (callback) {
  12. callback(u)
  13. }
  14. let neighbors = this.adjList.get(u)
  15. neighbors.map(val => {
  16. if (color[val] === "white") {
  17. this.dfsVisit(val, color, callback)
  18. }
  19. })
  20. color[u] = "black"
  21. }

</>复制代码

  1. 深度优先的原则以栈为数据结构

基本思想如下
1.初始化各个顶点的颜色(白色 - 未访问; 灰色 - 已发现; 黑色 - 已经探索完)
2.对顶点进行遍历并进行dfsVisit函数探索
3.优先进行最新探索的边进行深度探索,完成后标记探索完成

基本步骤如下
探索A
发现BCD
探索B
发现EF
探索E
发现I
探索I,完毕 标记I为以探索
回到上个分支遍历接着执行探索F
完成
标记F为以探索
。。。
直到返回到顶点A

完成探索

具体还有PLus版的深度和广度优先的算法,具体代码奉上

</>复制代码

  1. /*
  2. * @Author: koala_cpx
  3. * @Date: 2019-01-24 10:48:01
  4. * @Last Modified by: koala_cpx
  5. * @Last Modified time: 2019-01-24 10:56:33
  6. */
  7. class Dictionary {
  8. constructor () {
  9. this.items = {}
  10. }
  11. has (key) {
  12. return key in this.items
  13. }
  14. set (key, val) {
  15. this.items[key] = val
  16. }
  17. delete (key) {
  18. if (this.has(key)) {
  19. delete this.items[key]
  20. return true
  21. } else {
  22. return false
  23. }
  24. }
  25. get (key) {
  26. return this.has(key)? this.items[key] : undefined
  27. }
  28. values () {
  29. let values = []
  30. for (let k in this.items) {
  31. if (this.has(k)) {
  32. values.push(this.items[k])
  33. }
  34. }
  35. return values
  36. }
  37. }
  38. class Queue {
  39. constructor () {
  40. this.items = []
  41. }
  42. enqueue (element) {
  43. this.items.push(element)
  44. }
  45. dequeue () {
  46. return this.items.shift()
  47. }
  48. isEmpty() {
  49. return this.items.length === 0
  50. }
  51. }
  52. class Graph {
  53. constructor () {
  54. this.vertices = []
  55. this.adjList = new Dictionary()
  56. this.time = 0
  57. }
  58. addVertex (v) {
  59. this.vertices.push(v)
  60. this.adjList.set(v, [])
  61. }
  62. addEdge (v, w) {
  63. this.adjList.get(v).push(w)
  64. // this.adjList.get(w).push(v)
  65. }
  66. BFS (v, callback) {
  67. let color = this.initializeColor(),
  68. queue = new Queue()
  69. queue.enqueue(v)
  70. while (!queue.isEmpty()) {
  71. let u = queue.dequeue(),
  72. neighbors = this.adjList.get(u)
  73. color[u] = "grey"
  74. neighbors.map(val => {
  75. if (color[val] === "white") {
  76. color[val] = "grey"
  77. queue.enqueue(val)
  78. }
  79. })
  80. color[u] = "black"
  81. if (callback) {
  82. callback(u)
  83. }
  84. }
  85. }
  86. BFSPlus (v) {
  87. let color = this.initializeColor(),
  88. queue = new Queue(),
  89. d = [],
  90. pred = []
  91. queue.enqueue(v)
  92. this.vertices.map(val => {
  93. d[val] = 0
  94. pred[val] = null
  95. })
  96. while (!queue.isEmpty()) {
  97. let u = queue.dequeue(),
  98. neighbors = this.adjList.get(u)
  99. color[u] = "grey"
  100. neighbors.map(val => {
  101. if (color[val] === "white") {
  102. color[val] = "grey"
  103. d[val] = d[u] + 1
  104. pred[val] = u
  105. queue.enqueue(val)
  106. }
  107. })
  108. color[u] = "black"
  109. }
  110. return {
  111. distances: d,
  112. predecessors: pred
  113. }
  114. }
  115. DFS (callback) {
  116. let color = this.initializeColor()
  117. this.vertices.map(val => {
  118. if (color[val] === "white") {
  119. this.dfsVisit(val, color, callback)
  120. }
  121. })
  122. }
  123. DFSPlus () {
  124. let color = this.initializeColor(),
  125. d = [],
  126. f = [],
  127. p = []
  128. this.time = 0
  129. this.vertices.map(val => {
  130. f[val] = 0
  131. d[val] = 0
  132. p[val] = null
  133. })
  134. this.vertices.map(val => {
  135. if (color[val] === "white") {
  136. this.dfsPlusVisit(val, color, d, f, p)
  137. }
  138. })
  139. return {
  140. discovery: d,
  141. finished: f,
  142. predecessors: p
  143. }
  144. }
  145. dfsPlusVisit (u, color, d, f, p) {
  146. console.log("discovery" + u)
  147. color[u] = "grey"
  148. d[u] = ++this.time
  149. let neighbors = this.adjList.get(u)
  150. neighbors.map(val => {
  151. if (color[val] === "white") {
  152. p[val] = u
  153. this.dfsPlusVisit(val, color, d, f, p)
  154. }
  155. })
  156. color[u] = "black"
  157. f[u] = ++this.time
  158. console.log("explored" + u)
  159. }
  160. dfsVisit (u, color, callback) {
  161. color[u] = "grey"
  162. if (callback) {
  163. callback(u)
  164. }
  165. let neighbors = this.adjList.get(u)
  166. neighbors.map(val => {
  167. if (color[val] === "white") {
  168. this.dfsVisit(val, color, callback)
  169. }
  170. })
  171. color[u] = "black"
  172. }
  173. outPut(obj) {
  174. let fromVertex = this.vertices[0],
  175. { predecessors } = obj
  176. this.vertices.map(val => {
  177. let path = new Array()
  178. for (var v = val; v !== fromVertex; v = predecessors[v]) {
  179. path.push(v)
  180. }
  181. path.push(fromVertex)
  182. let s = path.pop()
  183. while (path.length !== 0) {
  184. s += " -- " + path.pop()
  185. }
  186. console.log(s)
  187. })
  188. }
  189. initializeColor () {
  190. let color = []
  191. this.vertices.map(val => {
  192. color[val] = "white"
  193. })
  194. return color
  195. }
  196. toString () {
  197. let s = ""
  198. for (let i = 0; i < this.vertices.length; i++) {
  199. s += this.vertices[i] + "->"
  200. let neighbors = this.adjList.get(this.vertices[i])
  201. for (let j = 0; j < neighbors.length; j++) {
  202. s += neighbors[j] + " "
  203. }
  204. s += "
  205. "
  206. }
  207. return s
  208. }
  209. }
  210. let a = new Dictionary()
  211. a.set("ss", 1111)
  212. a.set("s1", 1111)
  213. a.set("s2", 1112)
  214. a.set("s3", 1114)
  215. a.delete("s2")
  216. console.log(a.has("s3"))
  217. console.log(a.values())
  218. let graph = new Graph()
  219. let mv = ["A", "B", "C", "D", "E", "F", "G", "H", "I"]
  220. mv.map(val => {
  221. graph.addVertex(val)
  222. })
  223. graph.addEdge("A", "B")
  224. graph.addEdge("A", "C")
  225. graph.addEdge("A", "D")
  226. graph.addEdge("C", "D")
  227. graph.addEdge("C", "G")
  228. graph.addEdge("D", "G")
  229. graph.addEdge("D", "H")
  230. graph.addEdge("B", "E")
  231. graph.addEdge("B", "F")
  232. graph.addEdge("E", "I")
  233. console.log(graph.toString())
  234. function print(val) {
  235. console.log("vis" + val)
  236. }
  237. graph.BFS("A", print)
  238. console.log(graph.BFSPlus("A"))
  239. graph.outPut(graph.BFSPlus("A"))
  240. graph.DFS(print)
  241. console.log(graph.DFSPlus())
  242. let graph2 = new Graph()
  243. let mv2 = ["A", "B", "C", "D", "E", "F"]
  244. mv2.map(val => {
  245. graph2.addVertex(val)
  246. })
  247. graph2.addEdge("A", "C")
  248. graph2.addEdge("A", "D")
  249. graph2.addEdge("B", "D")
  250. graph2.addEdge("B", "E")
  251. graph2.addEdge("C", "F")
  252. graph2.addEdge("F", "E")
  253. let r = graph2.DFSPlus()
  254. console.log(r)

github直达地址 https://github.com/fanshyiis/...

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/101821.html

相关文章

  • 你该一点Javascript算法系列单源最短路径 - Dijkstra算法

    摘要:算法系列单源最短路径算法迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。 Javascript算法系列 - 单源最短路径 - Dijkstra算法 迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有...

    SoapEye 评论0 收藏0
  • 学习JavaScript数据结构算法 — 图

    摘要:图关联矩阵在关联矩阵表示的图中,矩阵的行表示顶点,列表示边。如图,顶点数是,边的数量是,用邻接矩阵表示图需要的空间是,而使用关联矩阵表示图需要的空间是。广度优先搜索算法数据结构是队列。深度优先搜索算法数据结构是栈。 定义 图和散列表、二叉树一样,是一种非线性数据结构。如图1所示,图由一系列顶点以及连接顶点的边构成。由一条边连接在一起的顶点成为相邻顶点,比如A和B、A和D是相邻的,而A和...

    yiliang 评论0 收藏0
  • 学习JavaScript数据结构算法深度优先搜索算法

    摘要:深度优先搜索上一次已经提到,图的遍历一般有两种算法,即广度优先和深度优先。用深度优先搜索算法对图中的任务图进行拓扑排序最终各顶点的发现和探索完成时间会保存在中。 深度优先搜索(DFS) 上一次已经提到,图的遍历一般有两种算法,即广度优先和深度优先。其中深度优先搜索算法会从第一个指定的顶点开始遍历图,沿着路径直到这条路径最后一个顶点,接着原路回退并探索下一条路径。换句话说,它是先深度后广...

    李增田 评论0 收藏0
  • 算法-图和图算法

    摘要:图的定义用图对现实中的系统建模可以用图对现实中的很多系统建模比如对交通流量建模顶点可以表示街道的十字路口边可以表示街道加权的边可以表示限速或者车道的数量建模人员可以用这个系统来判断最佳路线及最有可能堵车的街道任何运输系统都可以用图来建模比如 图的定义 用图对现实中的系统建模 可以用图对现实中的很多系统建模. 比如对交通流量建模, 顶点可以表示街道的十字路口, 边可以表示街道. 加权的边...

    Anshiii 评论0 收藏0
  • 学习JavaScript数据结构算法广度优先搜索算法

    摘要:广度优先搜索上一次已经提到,图的遍历一般有两种算法,即广度优先和深度优先。其中广度优先搜索算法会从指定的第一个顶点开始遍历图,先访问其所有的相邻点,就像一次访问图的一层。其它最短路径算法对于加权图的最短路径,广度优先算法可能并不合适。 广度优先搜索(BFS) 上一次已经提到,图的遍历一般有两种算法,即广度优先和深度优先。其中广度优先搜索算法会从指定的第一个顶点开始遍历图,先访问其所有的...

    eternalshallow 评论0 收藏0

发表评论

0条评论

qqlcbb

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<