图的JS实现

LeanCloud 发布于2019-08-21 17:00 / 2724人阅读

摘要：图的实现如下采用邻接表结构实现。由于本次示例的是无向图，因此每个顶点都互相增加为邻接点。然而由于本次示例的图为无向图，会出现重复遍历的情况，例如顶点的邻接点有，的邻接点有。

图的定义

图就是由若干个顶点和边连接起来的一种结构。很多东西都可以用图来说明，例如人际关系，或者地图。

其中图还分为有向图和无向图。
如下就是有向图

图的数据结构

对于图这种关系，可以通过两种方式来存储。

领接表

将每个顶点与其相邻的顶点存储起来。

邻接矩阵

将顶点间的相邻关系用0和1来表示，0表示不相邻，1表示相邻。

图的实现

如下采用邻接表结构实现。

构造函数

class Graph {
  constructor() {
    this.vertices = [];
    this.adjList = new Map();
  }
}

verrices存储所有的顶点，adjList存储顶点间的关系。

增

addVertex(v) {
  this.vertices.push(v);{1}
  this.adjList.set(v, []);{2}
}
addEdge(v, w) {
  this.adjList.get(v).push(w);
  this.adjList.get(w).push(v);
}

addVertex函数为新增顶点。{2}是为新增的顶点初始化一个为空的邻接点。
addEdge函数为关联两个顶点为邻接点。由于本次示例的是无向图，因此每个顶点都互相增加为邻接点。

遍历

图的遍历分为广度优先遍历和深度优先遍历。
广度优先遍历就是从一个顶点开始，一层一层的遍历顶点。而深度优先遍历，是从一个顶点开始，选择一个路径一直深入遍历，直到到达该路径的尽头，再返回去，按照同样的方式，遍历其他顶点。
无论广度优先还是深度优先，大致原理都是，创建一个字段，从一个顶点开始，将其邻接点一个个存入该字段中，唯一的区别是，广度优先遍历，该字段用队列存储，而深度优先遍历用栈存储。
然而由于本次示例的图为无向图，会出现重复遍历的情况，例如A顶点的邻接点有B，B的邻接点有A。因此需要创建一个类，来维护这些顶点哪些已经被遍历过了，哪些还没有遍历。

class GraphStatus {
  constructor() {
    this.status = {};
  }
  detect(key) {
    this.status[key] = true;
  }
  isDetected(key) {
    return !!this.status[key];
  }
}

如下是广度优先遍历

bfs(v, cb) {
   const queue = [],
    graphStatus = new GraphStatus();
  queue.push(v);
  while (queue.length > 0) {
     const u = queue.shift();
    graphStatus.detect(u);
    this.adjList.get(u).forEach(item => {
      if (!graphStatus.isDetected(item)) {
        graphStatus.detect(item);
        queue.push(item);
      }
    });
    if (cb) {
      cb(u);
    }
  }
}

如下是深度优先遍历

dfs(v, cb) {
   const stack = [],
    colorStatus = new GraphStatus();
  stack.push(v);
  while (stack.length > 0) {
    const u = stack.pop();
    colorStatus.detect(u);
    this.adjList.get(u).forEach(item => {
      if (!colorStatus.isDetected(item)) {
        colorStatus.detect(item);
        stack.push(item);
      }
    });
    cb(u);
  }
}

最短路径

基于广度优先遍历，可以很轻易的算出最短路径。

findDepth(v) {
   let queue = [],
    colorStatus = new GraphStatus(),
    vPath = { [v]: [v] },
    vDepth = {},
    depth = 0;
  queue.push(v);
  while (queue.length > 0) {
    depth++;
    const u = queue.shift();
    colorStatus.detect(u);
    // 相邻顶点
    const edgeVertex = this.adjList.get(u);
    edgeVertex.forEach(item => {
      if (!colorStatus.isDetected(item)) {
        // 深度统计
        vDepth[item] = depth;
        // 路径统计
        vPath[item] = [...vPath[u], item];
        colorStatus.detect(item);
        queue.push(item);
      }
    });
  }
  return { depth: vDepth, path: vPath };
}

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

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

JS -- 记一种用原生JS 实现轮播图的方法（非无限循环不自动切换）

摘要：实现一个非无限循环不自动切换的轮播图只需要几张图片和两个按钮简化部分两个按钮，几张图片假如有四张图右侧按钮左侧按钮部分动态添加删除的属性部分已是最后一张图这是第一张图实现一个非无限循环不自动切换的轮播图只需要几张图片和两个按钮（简化） HTML部分两个按钮，几张图片（假如有四张图）右侧按钮左侧按钮 CSS部分动态...

hidogs 2019-08-23 10:44 评论0 收藏0
chart. js 官方文档中文译本

摘要：条形图条形图提供了一种显示以垂直长条表示的数据值的方式。这些属性用于设置特定数据集的显示效果。这样做将使所有创建的气泡图在此之后创建新的默认值。重要的是要注意，图表中的属性是不可缩放的。它表示在气泡图上对应的气泡的原始半径以像素为单位。条形图条形图提供了一种显示以垂直长条表示的数据值的方式。有时用于显示代表某一趋势的数据，并且可同时并排比较多个数据集。 { type: bar, d...

chengtao1633 2019-08-20 16:02 评论0 收藏0
chart. js 官方文档中文译本

摘要：条形图条形图提供了一种显示以垂直长条表示的数据值的方式。这些属性用于设置特定数据集的显示效果。这样做将使所有创建的气泡图在此之后创建新的默认值。重要的是要注意，图表中的属性是不可缩放的。它表示在气泡图上对应的气泡的原始半径以像素为单位。条形图条形图提供了一种显示以垂直长条表示的数据值的方式。有时用于显示代表某一趋势的数据，并且可同时并排比较多个数据集。 { type: bar, d...

isaced 2019-08-01 16:43 评论0 收藏0
D3.js绘制实时映射的缩略图

摘要：在做可视化的很多时候，我们需要在主图的一角设置一个缩略图来掌握全局情况。，缩略图的绘制完成，很简单的例子，按照这个思路可以完成大部分可视化的缩略图绘制。在做可视化的很多时候，我们需要在主图的一角设置一个缩略图来掌握全局情况。本次将使用力导向图作为例子，完成缩略图的实现。绘制的原理就是依靠主图的数据再画一个图出来，无需再次计算，只改变图形形态。最终效果主图节点拖动，缩略图跟着变化...

miqt 2019-08-21 16:47 评论0 收藏0