用js来实现那些数据结构15(图01)[通俗易懂]

其实在上一篇介绍树结构的时候,已经有了一些算法的相关内容介入。而在图这种数据结构下,会有更多有关图的算法,比如广度优先搜索,深度优先搜索最短路径算法等等。这是我们要介绍的最后一个数据结构。同时也是本系

大家好,又见面了,我是你们的朋友全栈君。

  其实在上一篇介绍树结构的时候,已经有了一些算法的相关内容介入。而在图这种数据结构下,会有更多有关图的算法,比如广度优先搜索,深度优先搜索最短路径算法等等。这是我们要介绍的最后一个数据结构。同时也是本系列最为复杂的一个。那么我们先来简单介绍一下,什么是图?

 

一、图的概念

  简单说,就是网络结构的抽象模型,图是一组由连接的节点(或顶点)。任何二元关系都可以用图来表示。比如我们的地图,地铁线路图等。都是图的实际应用。

  接着我们看看图的一些相关概念和术语。

  一个图G = (V,E)由以下元素组成:

    V:一组顶点。

    E:一组边,链接V中的顶点。

  在继续之前我们先来上张图,继续我们的看图说话。

用js来实现那些数据结构15(图01)[通俗易懂]

   请看上图,我们来解释一些概念。

    1、由一条边连接在一起的顶点称为相邻顶点。比如上图中的A和B,A和C,A和D都是相邻的,但是A和E不是相邻的。

    2、一个顶点的取决于其相邻顶点的数量。也就是说,有多少个顶点与其相连,那么它的度就是多少。比如A的度是3,D的度就是4。

    3、路径是顶点V1,V2…..Vn的一个连续序列,其中Vi和Vi+1是相邻的。比如上图中的ACDG,ABEI都是一个路径。

    4、简单路径要求不包含重复的定点。比如ADG就是一条简单路径。

    5、除去最后一个顶点(因为它和第一个顶点时相同的),也是一个简单路径,比如ADCA。

    6、如果图中不存在环。则该图是无环的。

    7、如果图中每两个顶点间都存在路径,则该图是连通的。

  为了便于对比,我又花了一张图。

用js来实现那些数据结构15(图01)[通俗易懂]

  跟第一幅图几乎是一样的,只不过我们在路径上加了点东西。

    8、图可以是有向的(边有方向)或者是无向的(边没有方向)。比如上图我们在边上加了方向就变成了有向图。

    9、如果在图中的两个顶点间在双向上都存在路径,则该图是强连通的。比如上图中我们可以说C和D是强连通的。A和B不是强连通的。但是上图并不是一个强连通图。因为上图并不是两个点都有双向的路径。

    10、图还可以是未加权的或是加权的。上图边上加的数字就是加权值。(加权的意思可以简单理解为CSS选择器中的那种权重。)

 

二、图的表示方法

  我们可以表示图的方法有很多。根据我们要解决问题的类型和图的类型。我们可以选择不同的方法来表示图。下面我们会简单介绍两种表示图的方法。

  1、邻接矩阵。每一个节点都和一个整数相关联,该整数将作为数组的索引。我们用一个二维数组来表示各个顶点之间的连接情况。比如索引为i的节点和索引为j的节点相邻,则表示为arrya[i][j]=1。否则arrya[i][j]=0。

  用js来实现那些数据结构15(图01)[通俗易懂]

  邻接矩阵看起来就是这样子的。要注意我们上面的邻接矩阵只是表示两个顶点是否相邻。我们还需要一个数组来存储所有的顶点。

  但是邻接矩阵会有一些性能问题。比如我们会用很多的空间来表示一些根本就不存在的边。比如上图所有的0。再比如我们想要找到A顶点的相邻顶点,即使A顶点只有一个相邻顶点。我们也必须遍历整个数组才能找到。

  2、邻接表,鉴于以上的问题。我们在本篇中所使用的图的表示方法就是邻接表。邻接表由图中每个顶点的相邻顶点列表所组成。我们可以用数组,链表,map或者hashMap来实现邻接表。

用js来实现那些数据结构15(图01)[通俗易懂]

  邻接表看起来就像是上图这样。

  那么我们知道了图的一些基本概念和我们要使用的图的表示方法。下面我们先来完成我们Graph类的架子。

function Map () {
    //......其他各种方法,详见前面的字典部分
}

//代码很简单,但是还是要解释一下。
function Graph() {
    //vertices数组存放我们图中所有的顶点
    var vertices = [];
    //adjList存放我们的邻接表。adjList会使用顶点来作为键,邻接顶点列表作为值
    var adjList = new Map();
    //添加顶点的方法。
    this.addVertices = function (v) {
        //存放到顶点数组中
        vertices.push(v);
        //生成一个还没有邻接顶点列表的Map,因为这时我们已经有顶点了,所以要生成以待使用
        adjList.set(v,[]);
    }
    //这里有个小细节我们需要注意,哦对,这是为图添加边的方法。要注意的是,实际上,在代码中,我们是没有一个东西(变量或者其他什么)来代表边的。
    //我们为两个顶点之间添加一个边实际上只是为两个顶点的邻接表中加入彼此。这样就代表了这两个顶点是相邻的。
    this.addEdge = function (v,w) {
        //而这里我们所实现的图是无向图,所以需要给两个顶点所对应的邻接表加入彼此。
        //而如果是有向图的话,只需要根据方向添加一个就可以了。
        adjList.get(v).push(w);
        adjList.get(w).push(v);
    }

    // 为了方便观察,我们再实现一个toString方法
    // 没啥好说的,双重循环遍历两个数组。
    this.toString = function () {
        var s = "";

        for(var i = 0;i < vertices.length;i++) {
            s += vertices[i] + "->";
            var neighbors = adjList.get(vertices[i]);
            for(var j = 0; j < neighbors.length; j++) {
                s += neighbors[j] + '  ';
            }
            s += '\n';
        }
        return s;
    }
}

//我们来试一下
var graph = new Graph();

var verticesArray = ['A','B','C','D','E','F','G','H','I'];

for(var i = 0; i < verticesArray.length; i++) {
    graph.addVertices(verticesArray[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());
/*
A->B  C  D  
B->A  E  F  
C->A  D  G  
D->A  C  G  H  
E->B  I  
F->B  
G->C  D  
H->D  
I->E  
*/

  那么我们就实现了Graph类中最简单的部分——如何添加顶点和边。大家会不会觉得有点简单了。嘿嘿…..有趣的还在后面,别急……

  好了,那么到这里这篇文章就结束了。下一篇文章我们再继续学习图的遍历。

 

  最后,由于本人水平有限,能力与大神仍相差甚远,若有错误或不明之处,还望大家不吝赐教指正。非常感谢!  

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

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/124418.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • spel表达式的用法_substring用法

    spel表达式的用法_substring用法SPEL运算符运算符类型运算符算术运算+、-、*、/、%、^关系运算<、>、==、<=、>=、lt、gt、eq、le、ge逻辑运算and、or、not、|条件运算?:(ternary)、?:(Elvis)正则表达式matchesdemo数值运算<!–+运算符:两个数字相加–><propertyname=”adjustedAmount”value=”#{counter.total+42}

  • ubuntu安装vscode并配置python环境(使用anaconda)「建议收藏」

    ubuntu安装vscode并配置python环境(使用anaconda)「建议收藏」参考文章和视频https://www.youtube.com/watch?v=h0HbFnb8bC8https://python.tutorials24x7.com/blog/how-to-install-visual-studio-code-for-python-on-ubuntustep1-安装VSCODE在terminal中输入sudosnapinstall–classiccode等待下载完成后,在terminal中输入code即可启动vscodestep2-安装插件参

  • kettle教程(1) 简单入门、kettle简单插入与更新。打开kettle

    kettle教程(1) 简单入门、kettle简单插入与更新。打开kettle本文要点:Kettle的建立数据库连接、使用kettle进行简单的全量对比插入更新:kettle会自动对比用户设置的对比字段,若目标表不存在该字段,则新插入该条记录。若存在,则更新。 Kettle简介:Kettle是一款国外开源的ETL工具,纯java编写,可以在Window、Linux、Unix上运行,数据抽取高效稳定。Kettle中文名称叫水壶,该项目的主程序员MATT希望把各种数…

  • EasyDSS流媒体服务器软件-正式环境安装部署攻略

    EasyDSS流媒体服务器软件-正式环境安装部署攻略EasyDSS流媒体服务器软件,提供一站式的转码、点播、直播、时移回放服务,极大地简化了开发和集成的工作。其中,点播功能主要包含:上传、转码、分发。直播功能主要包含:直播、录像,直播支持RTMP输入,RTMP/HLS/HTTP-FLV的分发输出;录像支持自定义保存时长、检索及下载。提供丰富的二次开发接口,基于JSON的封装及HTTP调用。提供播放鉴权、推流鉴权等安全保证。提供用户及相关权限管理…

  • stn专线和otn有什么区别_stn云专线是什么意思?

    stn专线和otn有什么区别_stn云专线是什么意思?云专线产品是指依托于STN(智能传送网),为客户提供灵活业务接入、灵活带宽、高可靠性及端到端质量保障的专线产品。STN云专线产品描述:依托于STN(智能传送网),为客户提供灵活业务接入、灵活带宽、高可靠性及端到端质量保障的二层以太专线产品。STN(SmartTransportNetwork)智能传送网,采用JIPRAN及PTN技术相结合发展起来的—种增强型分组组网技术,该技术可叠加在移动业…

    2022年10月19日
  • 图的数据结构_数据结构关于图的算法

    图的数据结构_数据结构关于图的算法图的定义和术语完全图:任意两个点都有一条边相连连通图(强连通图)连通分量(强连通分量)有向图和无向图的工程案例#include “pch.h”#include <iostream>using namespace std;//有向图 无向图 有向网 无向网enum GraphKing { DG, DN, UDG, UDN };//定义图…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号