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

pengkingli 2019-07-01

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

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

注意：顶点有时也称为节点或者交点，边有时也称为链接。

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

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

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

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

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

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

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

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

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

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

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

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

class Dictionary {
  constructor () {
    this.items = {}
  }

  has (key) {
    return key in this.items
  }

  set (key, val) {
    this.items[key] = val
  }

  delete (key) {
    if (this.has(key)) {
      delete this.items[key]
      return true
    } else {
      return false
    }
  }

  get (key) {
    return this.has(key)? this.items[key] : undefined
  }

  values () {
    let values = []
    for (let k in this.items) {
      if (this.has(k)) {
        values.push(this.items[k])
      }
    }
    return values
  }
}

class Queue {
  constructor () {
    this.items = []
  }

  enqueue (element) {
    this.items.push(element)
  }

  dequeue () {
    return this.items.shift()
  }

  isEmpty() {
    return this.items.length === 0
  }
}
Dictionary 字典类来辅助存贮键值对
Queue 队列类来存贮队列
//定义class Graph
class Graph {
  constructor () {
    this.vertices = []
    this.adjList = new Dictionary()
  }
}
定义Graph类并且在构造函数里初始化字段
vertices 存储点信息
adjList 存储顶点间的链接关系
addVertex (v) {
    this.vertices.push(v)
    this.adjList.set(v, [])
  }

  addEdge (v, w) {
    this.adjList.get(v).push(w)
  }
addVertex 添加顶点的方法，存贮在数组vertices，并且初始化adjList字典里的值
addEdge 添加单向边 接收两个值 在邻接字典里加上从第一个顶点到第二个的关系

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

et graph = new Graph()
let mv = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
mv.map(val => {
  graph.addVertex(val)
})
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')

得到的图

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

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

toString () {
    let s = ''
    for (let i = 0; i < this.vertices.length; i++) {
      s += this.vertices[i] + '->'
      let neighbors = this.adjList.get(this.vertices[i])
      for (let j = 0; j < neighbors.length; j++) {
        s += neighbors[j] + ' '
      }
      s += '\n'
    }
    return s
  }
执行文件 node graph.js

得到结果

A->B C D 
B->E F 
C->D G 
D->G H 
E->I 
F->
G->

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

广度优先 - 数据结构 队列

先上代码

BFS (v, callback) {
    let color = this.initializeColor(),
        queue = new Queue()
    queue.enqueue(v)

    while (!queue.isEmpty()) {
      let u = queue.dequeue(),
          neighbors = this.adjList.get(u)
      color[u] = 'grey'
      neighbors.map(val => {
        if (color[val] === 'white') {
          color[val] = 'grey'
          queue.enqueue(val)
        }
      })
      color[u] = 'black'
      if (callback) {
        callback(u)
      }
    }
  }

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

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

直到所有顶点探索完

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

深度优先 - 数据结构 栈

先上代码

DFS (callback) {
    let color = this.initializeColor()
    this.vertices.map(val => {
      if (color[val] === 'white') {
        this.dfsVisit(val, color, callback)
      }
    })
  }

  dfsVisit (u, color, callback) {
    color[u] = 'grey'
    if (callback) {
      callback(u)
    }
    let neighbors = this.adjList.get(u)
    neighbors.map(val => {
      if (color[val] === 'white') {
        this.dfsVisit(val, color, callback)
      }
    })
    color[u] = 'black'
  }
深度优先的原则以栈为数据结构

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

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

完成探索

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

/*
* @Author: koala_cpx
* @Date:   2019-01-24 10:48:01
* @Last Modified by:   koala_cpx
* @Last Modified time: 2019-01-24 10:56:33
*/
class Dictionary {
  constructor () {
    this.items = {}
  }

  has (key) {
    return key in this.items
  }

  set (key, val) {
    this.items[key] = val
  }

  delete (key) {
    if (this.has(key)) {
      delete this.items[key]
      return true
    } else {
      return false
    }
  }

  get (key) {
    return this.has(key)? this.items[key] : undefined
  }

  values () {
    let values = []
    for (let k in this.items) {
      if (this.has(k)) {
        values.push(this.items[k])
      }
    }
    return values
  }
}

class Queue {
  constructor () {
    this.items = []
  }

  enqueue (element) {
    this.items.push(element)
  }

  dequeue () {
    return this.items.shift()
  }

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

class Graph {
  constructor () {
    this.vertices = []
    this.adjList = new Dictionary()
    this.time = 0
  }

  addVertex (v) {
    this.vertices.push(v)
    this.adjList.set(v, [])
  }

  addEdge (v, w) {
    this.adjList.get(v).push(w)
    // this.adjList.get(w).push(v)
  }

  BFS (v, callback) {
    let color = this.initializeColor(),
        queue = new Queue()
    queue.enqueue(v)

    while (!queue.isEmpty()) {
      let u = queue.dequeue(),
          neighbors = this.adjList.get(u)
      color[u] = 'grey'
      neighbors.map(val => {
        if (color[val] === 'white') {
          color[val] = 'grey'
          queue.enqueue(val)
        }
      })
      color[u] = 'black'
      if (callback) {
        callback(u)
      }
    }
  }

  BFSPlus (v) {
    let color = this.initializeColor(),
        queue = new Queue(),
        d = [],
        pred = []

    queue.enqueue(v)
    this.vertices.map(val => {
      d[val] = 0
      pred[val] = null
    })

    while (!queue.isEmpty()) {
      let u = queue.dequeue(),
          neighbors = this.adjList.get(u)
      
      color[u] = 'grey'
      neighbors.map(val => {
        if (color[val] === 'white') {
          color[val] = 'grey'
          d[val] = d[u] + 1
          pred[val] = u
          queue.enqueue(val)
        }
      })
      color[u] = 'black'
    }

    return {
      distances: d,
      predecessors: pred
    }
  }

  DFS (callback) {
    let color = this.initializeColor()
    this.vertices.map(val => {
      if (color[val] === 'white') {
        this.dfsVisit(val, color, callback)
      }
    })
  }

  DFSPlus () {
    let color = this.initializeColor(),
        d = [],
        f = [],
        p = []

    this.time = 0
    this.vertices.map(val => {
      f[val] = 0
      d[val] = 0
      p[val] = null
    })

    this.vertices.map(val => {
      if (color[val] === 'white') {
        this.dfsPlusVisit(val, color, d, f, p)
      }
    })

    return {
      discovery: d,
      finished: f,
      predecessors: p
    }
  }

  dfsPlusVisit (u, color, d, f, p) {
    console.log('discovery' + u)
    color[u] = 'grey'
    d[u] = ++this.time
    let neighbors = this.adjList.get(u)
    neighbors.map(val => {
      if (color[val] === 'white') {
        p[val] = u
        this.dfsPlusVisit(val, color, d, f, p)
      }
    })
    color[u] = 'black'
    f[u] = ++this.time
    console.log('explored' + u)
  }

  dfsVisit (u, color, callback) {
    color[u] = 'grey'
    if (callback) {
      callback(u)
    }
    let neighbors = this.adjList.get(u)
    neighbors.map(val => {
      if (color[val] === 'white') {
        this.dfsVisit(val, color, callback)
      }
    })
    color[u] = 'black'
  }

  outPut(obj) {
    let fromVertex = this.vertices[0],
        { predecessors } = obj
    this.vertices.map(val => {
      let path = new Array()
      for (var v = val; v !== fromVertex; v = predecessors[v]) {
        path.push(v)
      }
      path.push(fromVertex)
      let s = path.pop()
      while (path.length !== 0) {
        s += ' -- ' + path.pop()
      }
      console.log(s)
    })
  }

  initializeColor () {
    let color = []
    this.vertices.map(val => {
      color[val] = 'white'
    })
    return color
  }

  toString () {
    let s = ''
    for (let i = 0; i < this.vertices.length; i++) {
      s += this.vertices[i] + '->'
      let neighbors = this.adjList.get(this.vertices[i])
      for (let j = 0; j < neighbors.length; j++) {
        s += neighbors[j] + ' '
      }
      s += '\n'
    }
    return s
  }
}

let a = new Dictionary()
a.set('ss', 1111)
a.set('s1', 1111)
a.set('s2', 1112)
a.set('s3', 1114)

a.delete('s2')
console.log(a.has('s3'))

console.log(a.values())

let graph = new Graph()
let mv = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
mv.map(val => {
  graph.addVertex(val)
})
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())

function print(val) {
  console.log('vis' + val)
}

graph.BFS('A', print)
console.log(graph.BFSPlus("A"))
graph.outPut(graph.BFSPlus("A"))
graph.DFS(print)
console.log(graph.DFSPlus())

let graph2 = new Graph()
let mv2 = ['A', 'B', 'C', 'D', 'E', 'F']
mv2.map(val => {
  graph2.addVertex(val)
})
graph2.addEdge('A', 'C')
graph2.addEdge('A', 'D')
graph2.addEdge('B', 'D')
graph2.addEdge('B', 'E')
graph2.addEdge('C', 'F')
graph2.addEdge('F', 'E')

let r = graph2.DFSPlus()
console.log(r)

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

pengkingli

pengkingli

相关推荐

广度优先搜索原理与实践

在深度优先搜索原理与实践文章介绍了深度优先搜索算法的理论和实践。本文将介绍与其原理类似的广度优先搜索算法。其别名又叫 BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找

ustbfym / 0评论 2020-05-04

邻接表的深度优先算法和广度优先算法--p140和p142

#define vnum 100typedef char VerTexType;//定义链接队列的结点typedef struct LinkQueueNode{ int data1; struct LinkQueueNode *next;}LKQueNod

风吹夏天 / 0评论 2019-12-05

【算法】算法图解笔记_广度优先搜索

解决最短路径问题的算法被称为广度优先搜索。广度优先搜索算法最早由Edward F. Moore 1959年在“如何从迷宫中寻找出路”这一问题中提出。广度优先搜索让你能够找出两样东西之间的最短距离。使用广度优先搜索可以:. 若找到，则表示你与芒果销售商有联系

swjtuzbko / 0评论 2019-07-01

「Python | 边学边敲边记，附教程」第二次：深度&&广度优先算法

深度优先搜索的主要特征就是，假设一个顶点有不少相邻顶点，当我们搜索到该顶点，我们对于它的相邻顶点并不是现在就对所有都进行搜索，而是对一个顶点继续往后搜索，直到某个顶点，他周围的相邻顶点都已经被访问过了，这时他就可以返回，对它来的那个顶点的其余顶点进行搜索。

frankwtq / 0评论 2019-06-28

深度和广度优先搜索算法

在社交网络中，有一个六度分割理论，具体是说，世界上任何互不相识的两人，平均只需要六步就能够建立起联系。一个用户的一度连接用户就是他的好友，二度连接用户就是他好友的好友，三度连接用户就是他好友好友的好友。图上的搜索算法，就是从图中的一个顶点出发，到另一个顶点

风和日丽 / 0评论 2019-06-29

算法系列——JavaScript中广度优先搜索思想实现

什么是广度优先搜索？如果只是是背概念，幼儿园的小朋友都能背下来念给你听。假设看这篇文章的都和我一样是个前端工程师，我们要从广度优先搜索中学到什么？如果你看完这篇文章能够回答这个问题，那么你已经看懂了。广度优先搜索不是排序算法，它和快速排序、选择排序、冒泡排

YUAN / 0评论 2019-06-26

学习JavaScript数据结构与算法 — 广度优先搜索算法

将v标注为被发现的（灰色） ，并将v入队列Q。如果Q非空，则运行以下步骤：。将u从队列Q中取出将u标注为被发现的（灰色）将u所有未被访问过的邻节点（白色）加入队列将u标注为已被探索的（黑色）我们用三种状态来反映顶点的状态：。因此在算法开始执行时，需要将所有

duyifei0 / 0评论 2019-06-21

广度优先搜索算法

var tb = [], o, r, c, n=0, newHash;var dir=[ [-1,0], [1,0], [0,-1], [0,1], [-1,-1], [1,1], [1,-1], [-1,1] ];

hang0 / 0评论 2011-02-14

Python｜一文简单看懂 深度&广度 优先算法（内附教程分享）

今天给大家分享的是，Python里深度/广度优先算法介绍及实现。深度优先搜索的实现可以利用递归很简单地实现。最后，想学习Python的小伙伴们！请关注+私信回复：“学习”就可以拿到一份我为大家准备的Python学习资料！

jinhangdev / 0评论 2019-03-14

Python｜一文简单看懂 深度&广度 优先算法

今天给大家分享的是，Python里深度/广度优先算法介绍及实现。深度优先搜索的主要特征就是，假设一个顶点有不少相邻顶点，当我们搜索到该顶点，我们对于它的相邻顶点并不是现在就对所有都进行搜索，而是对一个顶点继续往后搜索，直到某个顶点，他周围的相邻顶点都已经被

快乐的鱼儿学敲码 / 0评论 2019-01-05

JavaScript实现树的遍历算法示例【广度优先与深度优先】

本文实例讲述了JavaScript实现树的遍历算法。分享给大家供大家参考，具体如下：。var aRTree = aTree.slice,iRNode = iNode,iLevel = 1;更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《J

小丫00 / 0评论 2017-10-26

Python数据结构与算法之图的广度优先与深度优先搜索算法示例

本文实例讲述了Python数据结构与算法之图的广度优先与深度优先搜索算法。分享给大家供大家参考，具体如下：。for all edges from v to w in G.adjacentEdges do. 4 if vertex w is not

HTML学堂码匠 / 0评论 2017-12-14

python 递归深度优先搜索与广度优先搜索算法模拟实现

# 问题：输入一个大于1 的数，求1+2+3+....取出栈内还未出栈的元素，即达到深度优先遍历。A先进队，在A出队的时候，C B入队，按图示，C出队，FG 入队，B出队，DE入队，F出队，JK入队，G出队，无入队，D出队，H I入队，最后E J K H

campwin / 0评论 2018-10-22

PHP实现广度优先搜索算法(BFS,Broad First Search)详解

本文实例讲述了PHP实现广度优先搜索算法。分享给大家供大家参考，具体如下：。广度优先遍历是连通图的一种遍历策略。因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域，故得名。广度优先搜索遍历类似于树的按层次遍历。然后顺序搜索访问w1的各未被访

PHP100 / 0评论 2019-03-28