内容字号:默认大号超大号

段落设置:段首缩进取消段首缩进

字体设置:切换到微软雅黑切换到宋体

详解图的JS实现

2017-10-12 17:05 出处:清屏网 人气: 评论(0

图的定义

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

其中图还分为有向图和无向图。

如下就是有向图

图的数据结构

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

领接表

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

邻接矩阵

将顶点间的相邻关系用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 };
}
分享给小伙伴们:
本文标签: JavaScript

相关文章

发表评论愿您的每句评论,都能给大家的生活添色彩,带来共鸣,带来思索,带来快乐。

CopyRight © 2015-2016 QingPingShan.com , All Rights Reserved.

清屏网 版权所有 豫ICP备15026204号