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

super.x

发布于 2019-04-12 15:19:36

6030

发布于 2019-04-12 15:19:36

文章被收录于专栏：考拉阅读前端团队考拉阅读前端团队考拉阅读前端团队

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

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

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

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

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

邻接列表：在邻接列表实现中，每一个顶点会存储一个从它这里开始的边的列表。比如，如果顶点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思想来实现图类

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

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')

得到的图

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

  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 。。。

直到所有顶点探索完

深度优先 - 数据结构栈

先上代码

  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/...

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

github