首页 / JAVASCRIPT / JavaScript 数据结构（十一）：图

相邻顶点 ：由一条边来连接在一起的顶点称为相邻顶点。
如上图里，a 与 b是相邻的，a 与 c 是相邻的，但 a 与 d 不是相邻的。
度：一个顶点度是其相邻顶点的数量。
如上图里 a 与两个顶点相邻，那么其度为2。b 与三个顶点相邻，那么其度为3。
路径：路径是顶点 v1，v2，…，vk的一个连续序列，其中 vi 和 vi + 1 是相邻的。
如上图所示，a,b,d,f 是一条简单的路径。
环：如果路径的最后一个顶点能重新回到该路径的第一个顶点，那么该路径称之为环。
如果图中不存在环，那么该图是无环的。如果图中每两个顶点都存在路径，则该图是联通的。

1、有向图与无向图

图可以是无向的（边没有方向，即无向图），也可以是有向的（即有向图，有向图的边至少有一个方向）。

我们可以观察一下下图。

JavaScript 数据结构（十一）：图 - 文章图片

在这个图里我们可以看见，A 与 E点是双向链接的，则证明此图是强连通的。

例如，A 与 E 是强连通的，A 与 B不是强连通的。

2、加权图与未加权图

图片也还可以是未加权的（上面的两个图都是未加权的）或是加权的（加权图的边被赋予了值）。

JavaScript 数据结构（十一）：图 - 文章图片

三、图的表示

从数据结构的角度来说，我们有很多方式来表示，在所有的表示法中，不存在绝对正确的方法。

图的正确表示法取决于待解决的问题和其类型。

1、邻接矩阵

图最常见的表示方法就是邻接矩阵。

这里我们可以参考下图。

JavaScript 数据结构（十一）：图 - 文章图片
不是强连通的图如果用邻接矩阵来表示，则矩阵中会有很多0，这意味着我们浪费了计算机的存储空间来表示根本不存在的边。

同样的，如果图中的顶点数里改变了，那么我们也不太好修改矩阵（二维数组不太灵活）。

2、邻接表

我们也可以使用 邻接表 来表示图。

邻接表由图中每个顶点的相邻点列表组成。

而这种数据结构存在好几种的实现方法。

我们可以用数组，链表，字典或是散列表来实现。

下图展示了邻接表的数据结构。

JavaScript 数据结构（十一）：图 - 文章图片

四、创建图类

照例声明一个类。

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

在 Graph 类的构造函数里，我们声明了三个变量。

isDirected 变量来表示图是否存在向，默认情况下图是无向的。

vertices 变量用来存储图中所欲顶点的名字。

adjList 字典（该字典我们在本系列第七篇中以实现）用来存储邻接表。

adjList 字典会使用顶点的名字作为键，邻接顶点列表作为值。

声明完后，我们来实现这么几个方法。

1、addVertex 方法

addVertex(v) {
    if ( this.vertices.includes(v) ) return;

    this.vertices.push(v);
    this.adjList.set(v,[]);
}

该方法用于创建一个顶点。

如果该值存在于图中，那么则不进行任何操作。‘

如果不存在，那么我们将这个值放入图中，并且为其对应的字典值设为一个空数组。

2、addEdge 方法

addEdge(v,w) {
    if ( !this.adjList.get(v) ) this.addVertex(v);
    if ( !this.adjList.get(w) ) this.addVertex(w);

    this.adjList.get(v).push(w);
    if ( !this.isDirected ) this.adjList.get(w).push(v);
}

该方法接收两个顶点作为参数，也就是说我们要建立链接的两个顶点。

在连接前，我们先要判定这两个顶点是否全部存在于图中，如若不存在，则去创建。

如若存在，则为第一个顶点对应的字典值放入第二个顶点。

并且如果图是无向的，那么第二个顶点对应的字典纸同样放入第一个顶点。

3、getVertices、getAdjList 与 toString 方法

如果要完成创建 Graph 类，那么我们还需要声明两个取值的方法：一个返回顶点列表，一个返回邻接表。

getVertices() { return this.vertices; }

getAdjList() { return this.adjList; }

toString() {
    let string = "";

    for ( let i = 0; i < this.vertices.length; i++ ) {
        string += `${this.vertices[i]} -> `;
        let neighbors = this.adjList.get(this.vertices[i]);
        for ( let j = 0; j < neighbors.length; j++ ) s += `${neighbors[j]}`;
        string += '\n';
    }

    return string;
}

当然了，还有一个方便我们查看的方法。

完成了这三个方法后让我们来测试一下以下的代码吧。

const graph = new Graph();
const vertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];

for (let i = 0; i < vertices.length; i++) graph.addVertex(vertices[i]);

graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I'); 

console.log(graph.toString());

其输出结果如下。

JavaScript 数据结构（十一）：图 - 文章图片

五、图的遍历

同树数据结构类似，我们可以访问图的所有节点。

其中，有两种算法可以对图进行遍历：广度优先搜索（Breadth-first Search，BFS） 和 深度优先搜索（Depth-first Search，DFS）。

图遍历算法的思想是必须追踪每个第一次访问的节点，并且追踪有哪些节点还没有被完全探索。

完全探索一个顶点要求我们查看该顶点的每一条边，对于每一条没有被访问过的，需将对其进行标记住待访问，并将其加入待访问的列表中。

为了保证算法的效率，每个顶点的访问次数尽量最多两次。连通图中每条边和顶点都会被访问到。

接下来，我们来创建一个常量，作为标记顶点状态的常量。

const Status = {
	toBeVisited : 0,// 未访问
	incompleteAccess : 1,// 未完全访问
	fullAccess ： 2// 完全访问
}

其次还需要一个函数来初始化每个顶点的状态。

const initializeStatus = vertices => {
    const statu = {};
    for ( let i = 0; i < vertices.length; i++ ) statu[vertices[i]] = Status.toBeVisited;
    return statu;
}

1、广度优先搜索

广度优先搜索算法会先宽后深的访问顶点。

理解了这个概念后，我们来实现广度优先搜索算法。

const breadthFirstSearch = (graph,starVertex,callback) => {
    let vertices = graph.getVertices(),
        adjList = graph.getAdjList(),
        statu = initializeStatus(vertices),
        queue = new Queue();

    queue.enqueue(starVertex);

    while ( !queue.isEmpty() ) {
        let u = queue.dequeue(),
            neighbors = adjList.get(u);
            
        statu[u] = Status.incompleteAccess;

        for ( let i = 0; i < neighbors.length; i++ ) {
            let w = neighbors[i];
            if ( statu[w] === Status.toBeVisited ) {
                statu[w] = Status.incompleteAccess;
                queue.enqueue(w);
            }
        }
        statu[u] = Status.fullAccess;
        if ( callback ) callback(u);
    }
}

breadthFirstSearch 方法接收一个图实例和顶点作为算法的起始点。其起始点是必要的，我们需要将他加入队列，其次就是遍历。

不过在遍历前，我们需要用 initializeStatusv 函数来将 statu 数组初始化为未访问状态。

与此同时我们还需要声明一个 Queue 实例来存储待访问和待探索的顶点。

声明完这两个变量后，我们就可以开始进行遍历了。

如果队列非空，那么我们将通过队列操作从队列中移除一个顶点，并取得一个包含其所有邻接点的表。再将该顶点标注为未完全访问，表示我们已经访问了，但未完全探索完。

当对该店全部探索完后，我们将该点标注为完全访问。

之后为了查看结果，我们为 breadthFirstSearch 方法还填充了一个可以接收回调函数的功能，方便我们来进行测试。

（1）、使用 BFS 寻找最短路径

上例中，我们展示了 BSF 算法的工作原理，那么接下来我们尝试用它做更多的事情。

例如，我们给定一个图 G 和源顶点 v，找出每个顶点 u 和 v 之间的最短路径的距离（以边的数里计算）。

对于给定顶点 v，广度优先算法会访问所有其距离为 1 的顶点，接着是距离为 2 的顶点，以此类推。

我们可以修改 breadthFirstSearch 方法返回给我们的信息：

从 v 到 u 的距离
前溯点 predecessors[u]。

让我们来看看改进后的广度优先方法的实现。

const BFS = (graph,starVertex) => {
    let vertices = graph.getVertices(),
        adjList = graph.getAdjList(),
        statu = initializeStatus(vertices),
        queue = new Queue(),
        distances = {},
        predecessors = {};

    queue.enqueue(starVertex);

    for ( let i = 0; i < vertices.length; i++ ) {
        distances[vertices[i]] = 0;
        predecessors[vertices[i]] = null;
    }

    while ( !queue.isEmpty() ) {
        let u = queue.dequeue(),
            neighbors = adjList.get(u);

        statu[u] = Status.incompleteAccess;

        for ( let i = 0; i < neighbors.length; i++ ) {
            let w = neighbors[i];
            if ( statu[w] === Status.toBeVisited ) {
                statu[w] = Status.incompleteAccess;
                distances[w] = distances[u] + 1;
                predecessors[w] = u;
                queue.enqueue(w);
            }
        }
        statu[u] = Status.fullAccess;
    }

    return {
        distances,
        predecessors
    }
}

改进后的 BFS 方法有什么改变呢？

首先是我们还需要声明数组 distances 来表示距离，以及 predecessors 数组来表示前溯点。

下一步则是对于图中的每个顶点的循环初始化。

用 0 来初始化数组 destances ，用 null 来初始化数组 predecessor。

之后当我们发现顶点 u 的邻点 w是，则设置 w 的前溯点为 u。并且我们通过给 distances[u] 加 1来增加 v 和 w 之间的距离。

最后返回一个包含 distances 和 predecessor 的对象。

2、深度优先搜索

深度优先搜索算法会先深后广的访问顶点。

理解了这个概念后，我们来实现深度优先搜索算法。

const depthFirstSearch = (graph,callback) => {
    let vertices = graph.getVertices(),
        adjList = graph.getAdjList(),
        statu = initializeStatus(vertices);

    for ( let i = 0; i < vertices.length; i++ ) {
        if ( statu[vertices[i]] === Status.toBeVisited ) {
            depthFirstSearchVisit(vertices[i],statu,adjList,callback);
        }
    }
}

const depthFirstSearchVisit = (u,statu,adjList,callback) => {
    statu[u] = Status.incompleteAccess;
    if ( callback ) callback(u);
    let neighbors = adjList.get(u);
    for ( let i = 0; i < Status.length; i++ ) {
        let w = neighbors[i];
        if ( statu[w] === Status.toBeVisited ) {
            depthFirstSearchVisit(w,color,adjList,callback);
        }
    }
    statu[u] = Status.fullAccess;
}

depthFirstSearch 方法接收一个图实例和回调函数作为参数。

在初始化每个顶点的颜色后，对于图实例中每一个违背访问过的顶点，我们调用私有的递归函数 depthFirstSearchVisit ，传递的参数为要访问的顶点 u、状态数组、邻接表与回调函数。

当访问顶点 u 时，我们标注其为未完全访问后，提取包含顶点 u 所有邻点的列表。

对于顶点 u 的每一个未被访问过的邻点 w。

我们将再次调用这个函数。

鉴于图的知识实在是太多了，这篇文章还需要好好整理一下再完善

标签：,,,,,,,, 来源： https://blog.csdn.net/weixin_44596681/article/details/112609759

内容总结

以上是互联网集市为您收集整理的JavaScript 数据结构（十一）：图全部内容，希望文章能够帮你解决JavaScript 数据结构（十一）：图所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/610794.html

来源：【匿名】

【上一篇】JavaScript常用事件及事件句柄【下一篇】javascript 怎么调用php方法

更多 ►

【JavaScript 数据结构（十一）：图】教程文章相关的互联网学习教程文章

JavaScript数据结构——队列的实现与应用【代码】

队列与栈不同，它遵从先进先出（FIFO——First In First Out）原则，新添加的元素排在队列的尾部，元素只能从队列头部移除。　　我们在前一篇文章中描述了如何用JavaScript来实现栈这种数据结构，这里我们对应地来实现队列。function Queue() {let items = [];// 向队列添加元素（一个或多个）this.enqueue = function (element) {if (element instanceof Array) items = items.concat(element);else items.push(element);};// 从队...

javascript数据结构-栈【代码】【图】

github博客地址栈（stack）又名堆栈，它是一种运算受限的线性表。遵循后进先出原则，像垃圾桶似的。功能实现依然按照增删改查来进行，内部数据存储可以借用语言原生支持的数组。栈类function Stack(){this.data = []; } 添加数据数据添加到末尾push: function (element){this.data.push(element); } 删除数据从末尾删除pop: function (){this.data.pop(); } 获取数据返回最后一个添加的peek: function (){return this.data[this.si...

JavaScript数据结构持续更新中。。一周后可完结【代码】

array：数组创建：var troop=new Array(6); //创建一个长度为6的数组var troop=new Array(2,3,5,6,4,7);数组方法：var str="I love javascript"; var single=str.split(""); //‘I‘,‘ ‘,‘l‘,‘o‘,.....var mutipy=str.split(" "); //‘I‘，‘love‘,‘javascript‘var troop=new Array(2,5,6,8,9,4,1,2); var index=troop.indexOf(2); //index=0var names=[‘jack‘,‘mike‘,‘mol...

javascript的基本语法、数据结构【代码】【图】

本篇学习资料主要讲解javascript的基本语法、数据结构无论是传统的编程语言，还是脚本语言，都具有数据类型、常量和变量、运算符、表达式、注释语句、流程控制语句等基本元素构成，这些基本元素构成了变成基础。一、javascript的基本语法1、执行顺序： javascript程序按照在html文件中出现的顺序逐行执行。如果需要在整个html文件中执行，最好将其放在<head>......</head>标记中。2、区分大小写：Javascript对字母大小写敏...

JavaScript数据结构——队列的实现【代码】【图】

前面楼主简单介绍了JavaScript数据结构栈的实现，http://www.cnblogs.com/qq503665965/p/6537894.html，本次将介绍队列的实现。　　队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。　　队列的两种主要操作是：向队列中插入新元素和删除队列中的元素。插入操作...

JavaScript数据结构之栈的用法示例【图】

本篇文章给大家带来的内容是关于JavaScript数据结构之栈的用法示例，有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。栈先来看一道题Leetcode 32 Longest Valid Parentheses (最长有效括号)给定一个只包含 ( 和 ) 的字符串，找出最长的包含有效括号的子串的长度。示例 1:输入: "(()"输出: 2解释: 最长有效括号子串为 "()"示例 2:输入: ")()())"输出: 4解释: 最长有效括号子串为 "()()"这道题可以用动态规划来做，也...

javascript-请问评论系统的层级数据结构要怎么取最合适？【图】

我想自己写一个wordpress的评论系统，当然是用wordpress的数据表结构了。但是在有个地方有点疑惑，就是如何去弄清这个层级。数据库结构如下其中id是自动生成的，postid表示评论在哪篇文章，approved表示是否过审（0表示没有），parent表示评论的父级Id（回复评论），content是内容。正常的输出效果应该是在这里，我应该如何写php，才可以达到这种效果...我就是脑里没有这种数据结构调用的概念。它的过程首先肯定是调用这个post...

js数据结构类型扩展immutable-js的使用介绍（代码示例）

本篇文章给大家带来的内容是关于js数据结构类型扩展immutable-js的使用介绍（代码示例），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。相对 java、.net 之类的强类型语言，js 有一点很大的区别就是，数据结构只有 array 与 object，并且都是动态可变的，而 java 有 List, Set, Map 等数据结构。所以，为了能在 js 中也使用这些数据结构，immutable-js 就应运而生。1. immutable-jsimmutable-js 扩充了 JavaScr...

详细解读javascript中map数据结构

本篇文章主要介绍了浅谈es6 javascript的map数据结构，小编觉得挺不错的，现在分享给大家，也给大家做个参考。一起跟随小编过来看看吧本文介绍了es6 javascript的map数据结构，分享给大家，具体如下：Map 结构的目的和基本用法JavaScript 的对象（ Object），本质上是键值对的集合（ Hash 结构），但是传统上只能用字符串当作键。这给它的使用带来了很大的限制。var data = {}; var element = document.getElementById(myp); ...

JS的数据结构

本文给大家分享的内容是关于js的数据结构，具有一定的参考价值，有需要的朋友可以参考一下一、标识符标识符，说白了，就是一个名字。在JavaScript中，变量和函数等都需要定义一个名字，这个名字就可以称为“标识符”。JavaScript语言中标识符最重要的3点就是：（1）第一个字符必须是字母、下划线（_）或美元符号这3种其中之一，其后的字符可以是字母、数字或下划线、美元符号；（2）变量名不能包含空格、加号、减号等符号；（3）...

详解JavaScript数据结构之字典类

字典是一种以“键–值”对形式存储数据的数据结构。就像电话薄里的名字和号码一样。JavaScript的Object类就是以字典的形式设计的。一、字典类字典类（Dictionary）基于Object。在《数据结构与算法JavaScript描述》书中“字典”采用了数组存储数据，不仅让阅读者很难理解，而且也没有实现便捷性，反而其中的代码逻辑是错误的，不能按照设计的方式正确输出结果！！！/*** 构造函数* 基于对象存储数据* @constructor*/function Dictio...

js数据结构和算法之数组和散列表详解【图】

一.数据结构1.什么是数据结构数据结构就是关系，没错，就是数据元素相互之间存在的一种或多种特定关系的集合。传统上，我们把数据结构分为逻辑结构和物理结构。逻辑结构：是指数据对象中数据元素之间的相互关系，也是我们今后最需要关注和讨论的问题。物理结构：是指数据的逻辑结构在计算机中的存储形式。2.常用的数据结构有：数组，队列（queue），堆（heap）,栈（stack），链表（linked list ），树（tree），图（graph）和散列表...

js数据结构和算法之栈和队列详解【图】

1.定义栈是一种重要的线性结构。栈（Stack）是一个后进先出（Last in first out,LIFO）的线性表，它要求只在表尾进行删除和插入操作。对于栈来说，这个表尾称为栈的栈顶，相应的表头称为栈底。栈的操作只能在这个线性表的表尾进行：栈的插入操作（Push），叫做进栈，也称为压栈，入栈。栈的删除操作（Pop），叫做出栈，也称为弹栈。2.栈的顺序存储结构因为栈的本质是一个线性表，线性表有两种存储形式，那么栈也有分为栈...

浅谈es6javascript的map数据结构_javascript技巧

本篇文章主要介绍了浅谈es6 javascript的map数据结构，小编觉得挺不错的，现在分享给大家JavaScript源码，也给大家做个参考。对JavaScript感兴趣的一起跟随小编过来看看吧本文介绍了es6 javascript的map数据结构，分享给大家，具体如下：Map 结构的目的和基本用法JavaScript 的对象（ Object），本质上是键值对的集合（ Hash 结构），但是传统上只能用字符串当作键。这给它的使用带来了很大的限制。var data = {}; var element...

js实现数据结构:树和二叉树,二叉树的遍历和基本操作方法【图】

树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结构。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等首先看看树的一些概念：1.树（Tree）是n（n>=0）个结点的有限集。在任意一棵非空树中：　　（1）有且仅有一个特定的称为根（Root）的结点；　　（2）当n>1时，其余结点可分...

首页 / JAVASCRIPT / JavaScript 数据结构（十一）：图

JavaScript 数据结构（十一）：图

内容导读

内容图文

JavaScript 数据结构系列目录

文章目录

一、图的概述

二、图的相关术语

1、有向图与无向图

2、加权图与未加权图

三、图的表示

1、邻接矩阵

2、邻接表

四、创建图类

1、addVertex 方法

2、addEdge 方法

3、getVertices、getAdjList 与 toString 方法

五、图的遍历

1、广度优先搜索

（1）、使用 BFS 寻找最短路径

2、深度优先搜索

内容总结

内容备注

内容手机端

【JavaScript 数据结构（十一）：图】教程文章相关的互联网学习教程文章

JAVASCRIPT - 相关标签

数据结构 - 相关标签

JAVASCRIPT - 技术教程分类

JAVASCRIPT - 最新教程

JAVASCRIPT - 最热教程