javascript数据结构-图

本博客参考于洛伊安妮·格罗纳编著的javascript数据结构与算法第三版及codeWay老师视频或其他博客资料，在此对此表示感谢!
github仓库：https://github.com/hzx17/

图

图的概念

在计算机程序设计中，图也是一种非常常见的数据结构，图论其实是一个非常大的话题，在数学上起源于哥尼斯堡七桥问题。

什么是图？

• 图是一种与树有些相似的数据结构。

  • 实际上，在数学的概念上，树是图的一种。
  • 我们知道树可以用来模拟很多现实的数据结构，比如：家谱/公司组织架构等等。

• 那么图长什么样子呢？或者什么样的数据使用图来模拟更合适呢？

  • 人与人之间的关系网
    

  • 互联网中的网络关系
    

  • 地铁图

  • ……

• 那么，什么是图呢?

  • 我们会发现，上面的结点（其实图中叫顶点 Vertex）之间的关系，是不能使用树来表示（几叉树都不可以）。
  • 这个时候，我们就可以使用图来模拟它们。

• 图通常有什么特点呢？

  • 一组顶点：通常用 V (Vertex) 表示顶点的集合
  • 一组边：通常用 E (Edge) 表示边的集合
  • 边是顶点和顶点之间的连线
  • 边可以是有向的，也可以是无向的。（比如 A — B，通常表示无向。 A –> B，通常表示有向）

图的术语

术语

• 我们在学习树的时候，树有很多的其他术语，了解这些术语有助于我们更深层次的理解图。

• 但是图的术语其实非常多，如果你找一本专门讲图的各个方面的书籍，会发现只是术语就可以占据一个章节。

• 这里，这里介绍几个比较常见的术语，某些术语后面用到的时候，再了解，没有用到的，不做赘述。

• 下面这是个抽象出来的图
  

• 顶点

  • 顶点刚才我们已经介绍过了，表示图中的一个结点。
  • 比如地铁站中某个站/多个村庄中的某个村庄/互联网中的某台主机/人际关系中的人。

• 边

  • 边表示顶点和顶点之间的连线。
  • 比如地铁站中两个站点之间的直接连线, 就是一个边。
  • 注意：这里的边不要叫做路径，路径有其他的概念，后面会区分。

• 相邻顶点

  • 由一条边连接在一起的顶点称为相邻顶点。
  • 比如 0 - 1 是相邻的，0 - 3 是相邻的。0 - 2 是不相邻的。

• 度

  • 一个顶点的度是相邻顶点的数量
  • 比如 0 顶点和其他两个顶点相连，0 顶点的度是 2
  • 比如 1 顶点和其他四个顶点相连，1 顶点的度是 4

• 路径

  • 路径是顶点 v1，v2…，vn 的一个连续序列, 比如上图中 0 1 5 9 就是一条路径。
  • 简单路径: 简单路径要求不包含重复的顶点. 比如 0 1 5 9 是一条简单路径。
  • 回路：第一个顶点和最后一个顶点相同的路径称为回路。比如 0 1 5 6 3 0。

• 无向图

  • 上面的图就是一张无向图，因为所有的边都没有方向。
  • 比如 0 - 1 之间有边，那么说明这条边可以保证 0 -> 1，也可以保证 1 -> 0。

• 有向图

  • 有向图表示的图中的边是有方向的。
  • 比如 0 -> 1，不能保证一定可以 1 -> 0，要根据方向来定。

无权图和带权图

• 无权图

  • 我们上面的图就是一张无权图（边没有携带权重）
  • 我们上面的图中的边是没有任何意义的，不能收 0 - 1 的边，比 4 - 9 的边更远或者用的时间更长。

• 带权图

  • 带权图表示边有一定的权重
  • 这里的权重可以是任意你希望表示的数据：比如距离或者花费的时间或者票价。
  • 我们来看一张有向和带权的图
    

现实建模

• 对交通流量建模

  • 顶点可以表示街道的十字路口，边可以表示街道.。
  • 加权的边可以表示限速或者车道的数量或者街道的距离。
  • 建模人员可以用这个系统来判定最佳路线以及最可能堵车的街道。

• 对飞机航线建模

  • 航空公司可以用图来为其飞行系统建模。
  • 将每个机场看成顶点，将经过两个顶点的每条航线看作一条边。
  • 加权的边可以表示从一个机场到另一个机场的航班成本，或两个机场间的距离。
  • 建模人员可以利用这个系统有效的判断从一个城市到另一个城市的最小航行成本。
    ​

图的表示

我们知道一个图包含很多顶点，另外包含顶点和顶点之间的连线（边），这两个都是非常重要的图信息，因此都需要在程序中体现出来。

顶点表示

• 顶点的表示相对简单

  • 上面的顶点，我们抽象成了 1 2 3 4，也可以抽象成 A B C D。在后面的案例中，我们使用 A B C D。
  • 那么这些 A B C D 我们可以使用一个数组来存储起来(存储所有的顶点)。
  • 当然，A B C D 有可能还表示其他含义的数据(比如村庄的名字)，这个时候，可以另外创建一个数组，用于存储对应的其他数据。

• 边的表示略微复杂

  • 因为边是两个顶点之间的关系，所以表示起来会稍微麻烦一些。
  • 下面是变常见的表示方式。

邻接矩阵

• 概述

  • 邻接矩阵让每个节点和一个整数向关联, 该整数作为数组的下标值.
  • 我们用一个二维数组来表示顶点之间的连接.
  • 演示
    

• 图片解析

  • 在二维数组中，0 表示没有连线，1 表示有连线。
  • 通过二维数组，我们可以很快的找到一个顶点和哪些顶点有连线。（比如 A 顶点, 只需要 遍历第一行即可）
  • 另外，A - A，B - B（也就是顶点到自己的连线），通常使用 0 表示。

• 邻接矩阵的问题

  • 如果是一个无向图，邻接矩阵展示出来的二维数组，其实是一个对称图。

    • 也就是 A -> D 是 1 的时候，对称的位置 D -> 1 一定也是 1。
    • 那么这种情况下会造成空间的浪费，解决办法需自己去研究下。

  • 邻接矩阵还有一个比较严重的问题就是如果图是一个稀疏图

    • 那么矩阵中将存在大量的 0，这意味着我们浪费了计算机存储空间来表示根本不存在的边。
    • 而且即使只有一个边，我们也必须遍历一行来找出这个边，也浪费很多时间。

邻接表

• 概述

  • 邻接表由图中每个顶点以及和顶点相邻的顶点列表组成。
  • 这个列表有很多中方式来存储：数组/链表/字典(哈希表)都可以。
  • 演示
    

• 图片解析

  • 其实图片比较容易理解
  • 比如我们要表示和 A 顶点有关联的顶点（边），A 和 B/C/D 有边，那么我们可以通过 A 找到 对应的数组/链表/字典，再取出其中的内容就可以啦。

• 邻接表的问题

  • 邻接表计算“出度”是比较简单的（出度：指向别人的数量, 入度: 指向自己的数量）
  • 邻接表如果需要计算有向图的“入度”，那么是一件非常麻烦的事情。
  • 它必须构造一个“逆邻接表”，才能有效的计算“入度”。而临街矩阵会非常简单。

图的封装

 /* 封装队列类 */
 function Queue(){
  //属性
  this.items=[];
  /* 方法 */
  //将元素放入队列中
  Queue.prototype.enqueue=function(element){
      this.items.push(element)
  }
  //从队列中删除前端元素
  Queue.prototype.dequeue=function(){
  return this.items.shift();
}
  //从队列中查看前端元素
  Queue.prototype.showqueue=function(){
      return this.items[0]
}
//从队列中删除任何位置元素
Queue.prototype.spliceelement=function(index,count){
  return this.items.splice(index,count)
}
  //查看队列中元素个数是否为空
  Queue.prototype.isEmpty=function(){
    return this.items.length==0
}
  //查看队列中的元素个数
  Queue.prototype.elementnum=function(){
  return this.items.length;
  }
  //toString
  Queue.prototype.toString=function(){
    let resultString="";
    for(var i=0;i<this.items.length;i++){
        resultString +=this.items[i]+""
    }
    return resultString
}
}

/* 封装图 */
function Graph () {
  // 属性：顶点
  this.vertexes = [] // 顶点
  this.edges = new Map() // 边-字典类

  // 往图中添加边
  Graph.prototype.addVertexes = function (v){
    this.vertexes.push(v)
    this.edges.set(v,[])
  }
  // 往图中添加边
  Graph.prototype.addEdges = function (v1,v2) {
    this.edges.get(v1).push(v2)
    this.edges.get(v2).push(v1)
  }
  // 图结构的toString方法
  Graph.prototype.toString = function () {
    // 定义一个字符串，保存最终的结果
    let resultString = ""
    // 遍历边结构
    for(let i = 0 ; i< this.vertexes.length ;i++) {
      resultString += this.vertexes[i] + "->"
      resultString += this.edges.get(this.vertexes[i]) + `\n`
    }
    return resultString
  }
  // 初始化颜色
  Graph.prototype.initializeColor = function () {
    // 定义颜色数组
    let colors= [] 
    for( let i = 0 ;i<this.vertexes.length ;i++) {
      colors[this.vertexes[i]] = 'white' // 白色标识未处理
    }
    return colors
  }
  //广度优先搜索遍历 - 队列实现
  Graph.prototype.breadthFirstSearch = function (initv,handler) {
    let colors = this.initializeColor() // 初始化颜色
    //创建一个队列
    const queue = new Queue()
    // 将顶点加入到队列中
    queue.enqueue(initv)
    // 循环取出队列
    while(!queue.isEmpty()) {
      // 取出顶点
      let v= queue.dequeue()
      // 获取顶点与顶点相邻的其他顶点
      let vlist = this.edges.get(v)
      colors[v] = "gray" // 灰色标识为已探测
      for(let i = 0; i<vlist.length ;i++){
        let e = vlist[i]
        if( colors[e] == 'white') {
          colors[e] = 'gray'
          queue.enqueue(e)
        }
      }
      // 访问原点，处理函数
      handler(v)
      colors[v] = 'black'
    }
  }

  // 图的深度优先遍历 - 栈或递归实现 -这里我们使用递归来实现
  Graph.prototype.depthFristSearch = function (initv,handler) {
    let colors = this.initializeColor() // 初始化颜色
    // 从某个节点开始递归
    this.reDepthFristSearch(colors,initv,handler)
  }
  // 深度优先遍历递归函数
  Graph.prototype.reDepthFristSearch = function (colors,v,handler) {
    colors[v] = 'gray'
    handler(v)
    let vlist = this.edges.get(v)
    for(let i= 0;i<vlist.length ;i++) {
       let e = vlist[i]
       if(colors[e] =="white") {
         this.reDepthFristSearch(colors,e,handler)
         colors[e] = 'black'
       }
    }
  } 
} 

测试图

/* 测试代码 */
const graph = new Graph()

let vertexes = ["A","B","C","D","E","F","G","H","I"]
for(let i = 0 ;i < vertexes.length ; i++){
  graph.addVertexes(vertexes[i])
}
graph.addEdges("A","B")
graph.addEdges("A","C")
graph.addEdges("A","D")
graph.addEdges("C","D")
graph.addEdges("D","G")
graph.addEdges("D","H")
graph.addEdges("B","E")
graph.addEdges("B","F")
graph.addEdges("E","I")
console.log(graph.toString())
// console.log(graph)  
//广度优先
console.log('广度优先：')
graph.breadthFirstSearch("A" , function (v) {
  console.log(v)
})
// 深度优先
console.log('深度优先：')
graph.depthFristSearch("A" , function (v) {
  console.log(v)
})