JS中数据结构之图

更新日期: 2019-01-23阅读: 2k标签: 数据结构

图由边的集合及顶点的集合组成。边是有方向的是有序图(有向图),否则就是无序图(无向图)。图中的一系列顶点构成路径,路径中所有的顶点都由边连接。路径的长度用路径中第一个顶点到最后一个顶点之间边的数量表示。

邻接表来表示边,即将与某一顶点的相邻的边表示为由该顶点的相邻顶点列表构成的数组,并以该顶点作为索引。比如,如果顶点 2 与顶点 0、 1、3、4 相连,那么就将0、1、3、4存储在数组中索引为 2 的位置。


Graph 类定义图

function Graph(v) {
  this.vertices = v;  //顶点的数量
  this.edges = 0;
  this.adj = [];
  for (var i = 0; i < this.vertices; ++i) {
    this.adj[i] = [];  //保存与顶点 i 相邻的顶点列表
  }
  this.addEdge = addEdge;
  this.showGraph = showGraph;
  this.dfs = dfs;
  this.bfs = bfs;
  this.marked = [];  //保存未访问过的顶点
  for (var i = 0; i < this.vertices; ++i) {
    this.marked[i] = false;
  }
  this.pathTo = pathTo;
  this.hasPathTo = hashPathTo;
  this.edgeTo = [];
}

addEdge(A,B) 添加边,先查找顶点 A 的邻接表,将顶点 B 添加到列表中,然后再查找顶点 B 的邻接表,将顶点 A 加入列表。最后,将边数加 1。

function addEdge(v, w) {
  this.ajd[v].push(w);
  this.adj[w].push(v);
  this.edges++;
}

showGraph() 方法显示所有顶点及其相邻顶点列表

function showGraph() {
  for (var i = 0; i < this.vertices; ++i) {
    var str = ‘‘;
    str += i + " -> ";
    for (var j = 0; j < this.vertices; ++j) {
      if (this.adj[i][j] != undefined) {
        str += this.adj[i][j] + ‘ ‘;
      }
    }
    console.log(str);
  }
}

搜索图

确定从一个指定的顶点可以到达其他哪些顶点,有两种搜索方法:深度优先搜索和广度优先搜索。

深度优先搜索从起始顶点开始追溯,直到到达最后一个顶点,然后回溯, 继续追溯下一条路径,直到到达最后的顶点,如此往复,直到没有路径为止。当访问一个没有访问过的顶点时,将它标记为已访问,再递归地去访问在初始顶点的邻接表中其他没有访问过的顶点。

function dfs(v) {
  this.marked[v] = true;
  if (this.adj[v] != undefined) {
    console.log("Visited vertex: " + v);
  }
  for(var w of this.adj[v]) {
    if (!this.marked[w]) {
      this.dfs(w);
    }
  }
}

//调用
g = new Graph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.showGraph();
g.dfs(0);

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

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

链接: https://www.fly63.com/article/detial/1870

数据结构有哪几种?

据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。包括三个组成成分:数据的逻辑结构、物理结构(存储结构)、数据运算结构。

为什么我认为数据结构与算法对前端开发很重要?

一个具有层级结构的数据,实现这个功能非常容易,因为这个结构和组件的结构是一致的,递归遍历就可以了。但是,由于后端通常采用的是关系型数据库,所以返回的数据通常会是这个样子:前端这边想要将数据转换一下其实也不难,因为要合并重复项

JS中数据结构之链表

数组不总是组织数据的最佳数据结构,在很多编程语言中,数组的长度是固定的,所以当数组已被数据填满时,再要加入新的元素就会非常困难。在数组中,添加和删除元素也很麻烦,因为需要将数组中的其他元素向前或向后平移。

ES6中的Set数据结构以及使用使用场景

Set 是ES6提供的一种新的数据结构,它允许你存储任何类型的唯一值,而且Set中的元素是唯一的。我们用new操作符来生成一个Set对象,set结构的实例有以下属性

JS数据结构与算法_链表

链表更加像是数组。链表和数组都是用于存储有序元素的集合,但有几点大不相同,链表的实现不像之前介绍的栈和队列一般依赖于数组(至少我们目前是这样实现的),它必须自己构建类并组织逻辑实现。我们先创建一个Node类

JS数据结构与算法_集合&字典

集合set是一种包含不同元素的数据结构。集合中的元素成为成员。集合的两个最重要特性是:集合中的成员是无序的;集合中不允许相同成员存在,计算机中的集合与数学中集合的概念相同,有一些概念我们必须知晓:

JS数据结构与算法_树

一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点(除了顶部的第一个节点)以及零个或多个子节点:关于数的深度和高度的问题,不同的教材有不同的说法

JavaScript数据结构与算法-String

给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。主要就是用到了数组的 split 、 reverse 、 join 、 map 方法,原理:就是把字符串变成数组

链表!比数组更适合做增删操作的数据结构

链表和数组的对比:在大多数语言中,数组的大小是固定的,从数组的起点或中间添加或删除元素的成本很高,因为需要移动元素,链表中的每一个元素在内存中不是连续放置的,和它左右两侧元素是没有关系的

数据结构与算法之绪论

什么是数据结构?简单来说可以解释为:程序设计=数据结构+算法;主要是用来研究数据结构的关系,数据元素之间存在的一种或多种特定关系的集合;

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!