专栏首页萌兔it数据结构与JS也可以成为CP(十)Graph图

数据结构与JS也可以成为CP(十)Graph图

我们先来看看图是什么吧~图由边和顶点的集合组成,

名词解释

1)有向图:一个图的顶点对是有序的。

2)无序图:图是无序的。

3)简单图:没有重复边、重复顶点的圈。

4)强连通:两个顶点之间有路径。

图的实现

下面看看图怎么实现吧!图是由顶点和边组成的,我们首先要实现顶点,然后实现边。

function Graph(v) {
  this.vertices = v;
  this.edges = 0;
  this.adj = [];
  for (var i = 0; i < this.vertices; ++i) {
     this.adj[i] = [];
     this.adj[i].push("");
  }
  this.addEdge = addEdge;
  this.showGraph = showGraph;
}
function addEdge(v, w) {
  this.adj[v].push(w);
  this.adj[w].push(v);
  this.edges++;
}
function showGraph() {
  for (var i = 0; i < this.vertices; ++i) {
    putstr(i + " -> ");
    for (var j = 0; j < this.vertices; ++j ) {
      if (this.adj[i][j] != undefined) { 
        putstr(this.adj[i][j] + ' ');
      } 
    }
    print(); 
  }
}

图的搜索

图的搜索包括深度优先搜索和广度优先搜索。

1)深度优先搜索算法比较简单:访问一个没有访问过的顶点,将它标记为已访问,再递归地去访问在初始顶点的邻接表中其他没有访问过的顶点。

function dfs(v) {
  this.marked[v] = true;
  for (var w in this.adj[v]) {
    if (!this.marked[w]) {
      this.dfs(w);
    } 
  }
}

2)广度优先搜索从第一个顶点开始,尝试访问尽可能靠近它的顶点。本质上,这种搜索在图上是逐层移动的,首先检查最靠近第一个顶点的层,再逐渐向下移动到离起始顶点最远的层。

function bfs(s) {
  var queue = []; this.marked[s] = true; queue.push(s); // 添加到队尾 
  while (queue.length > 0) {
    var v = queue.shift(); // 从队首移除 if (v == undefined) {
  }
  for (var w in this.adj[v]) {
    if (!this.marked[w]) {
      this.edgeTo[w] = v;
      this.marked[w] = true;
      queue.push(w);
    } 
  }
} 

图的应用

说了这么多,图能够用在哪里呢?

1)查找最短路径

2)拓扑排序

本文分享自微信公众号 - 萌兔it(mengtu_it),作者:萌兔IT

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • JavaScript入门总结第五弹——带你搞懂this

    Hello,小可爱们我又来了!今天的主题是一个非常困惑人的专题,this,想要弄清this的指向,也是一件不容易的事情。下面我们就开始正题了~~...

    萌兔IT
  • 数据结构于JS也可以成为CP(二)列表

    Hello小伙伴们~上次分享有小伙伴在后台留言说程序就是一个数据结构,怎么说呢,我觉得这是片面的,在生产中,我们往往会尽量避免在前端写业务逻辑,因为有些不安全,...

    萌兔IT
  • 数据结构于JS也可以成为CP(三)栈

    Hello小伙伴们大家好,今天要为大家带来的是栈,这是数据结构中常用到的一种结构。它和列表有一点相似,又有些不同。相对于列表来说,栈更加高效,为啥呢,因为栈只能...

    萌兔IT
  • 商品多种规格属性的选择(sku 算法)

    如上图中每一个单规格选项,例如==珍珠白==、==12GB+512GB==、==不分期==就是一个规格(sku)。商品和 sku 属于一对多的关系,也就是我们可...

    岚孩子
  • 求超大文件上传方案( B/S )

    需求:项目要支持大文件上传功能,经过讨论,初步将文件上传大小控制在500M内,因此自己需要在项目中进行文件上传部分的调整和配置,自己将大小都以501M来进行限制...

    用户6892318
  • vue轮播组件--不插电手动粘贴版

    轮播的原理是每一帧都选出一个当前元素,前一个元素,后一个元素然后排成一行,最后改变这三个元素的translate来触发css3的transition进行动画,当...

    Ganother
  • inputSuggest邮箱提示自动补全js插件

    deepcc
  • IScroll的那些事——内容不足时下拉刷新

    之前项目中的列表是采用的IScroll,但是在使用IScroll有一个问题就是:当内容不足全屏的时候,是木有办法往下拉的,这样就达不到刷新的目的了。【这是本人工...

    糊糊糊糊糊了
  • 学习 Phaser.js HTML5游戏开发-DAY3

    3. 构建基本的子弹对象,fire 方法用来初始化子弹实例,update方法用来绘制子弹轨迹

    tonglei0429
  • 左右滚动,带控制按钮

    今天需要一个左右滚动图的js,从网上着了半天,修改调试了半天才弄好,于是就收藏了。不过以后真得看看js了 关键代码有注释:(红色部分是我加的注释) <table...

    苦咖啡

扫码关注云+社区

领取腾讯云代金券