JavaScript实现图结构

JavaScript实现图结构JavaScript实现图结构一、图论1.1.图的简介什么是图?图结构是一种与树结构有些相似的数据结构; 图论是数学的一个分支,并且,在数学中,树是图的一种; 图论以图为研究对象,研究顶点和边组成的图形的数学理论和方法

JavaScript实现图结构

一、图论

1.1.图的简介

什么是图?

  • 图结构是一种与树结构有些相似的数据结构;
  • 图论是数学的一个分支,并且,在数学中,树是图的一种;
  • 图论以图为研究对象,研究顶点组成的图形的数学理论和方法;
  • 主要的研究目的为:事物之间的联系顶点代表事物代表两个事物间的关系

图的特点:

  • 一组顶点:通常用 V (Vertex)表示顶点的集合;
  • 一组边:通常用 E (Edge)表示边的集合;
    • 边是顶点和顶点之间的连线;
    • 边可以是有向的,也可以是无向的。比如A—-B表示无向,A —> B 表示有向;

图的常用术语:

  • 顶点:表示图中的一个节点

  • 边:表示顶点和顶点给之间的连线

  • 相邻顶点:由一条边连接在一起的顶点称为相邻顶点

  • 度:一个顶点的相邻顶点的数量

  • 路径:

    • 简单路径:简单路径要求不包含重复的顶点;
    • 回路:第一个顶点和最后一个顶点相同的路径称为回路;
  • 无向图:图中的所有边都是没有方向的;

  • 有向图:图中的所有边都是方向的;

  • 无权图:无权图中的边没有任何权重意义;

  • 带权图:带权图中的边有一定的权重含义;

1.2.图的表示

邻接矩阵

表示图的常用方式为:邻接矩阵

  • 可以使用二维数组来表示邻接矩阵;

  • 邻接矩阵让每个节点和一个整数相关联,该整数作为数组的下标值

  • 使用一个二维数组来表示顶点之间的连接

如上图所示:

  • 二维数组中的0表示没有连线,1表示有连线;
  • 如:A[ 0 ] [ 3 ] = 1,表示 A 和 C 之间有连接;
  • 邻接矩阵的对角线上的值都为0,表示A – A ,B – B,等自回路都没有连接(自己与自己之间没有连接);
  • 若为无向图,则邻接矩阵应为对角线上元素全为0的对称矩阵;

邻接矩阵的问题:

  • 如果图是一个稀疏图,那么邻接矩阵中将存在大量的 0,造成存储空间的浪费;

邻接表

另外一种表示图的常用方式为:邻接表

  • 邻接表由图中每个顶点以及和顶点相邻的顶点列表组成;
  • 这个列表可用多种方式存储,比如:数组/链表/字典(哈希表)等都可以;

 

如上图所示:

  • 图中可清楚看到A与B、C、D相邻,假如要表示这些与A顶点相邻的顶点(边),可以通过将它们作为A的值(value)存入到对应的数组/链表/字典中。
  • 之后,通过键(key)A可以十分方便地取出对应的数据;

邻接表的问题:

  • 邻接表可以简单地得出出度,即某一顶点指向其他顶点的个数;
  • 但是,邻接表计算入度(指向某一顶点的其他顶点的个数称为该顶点的入度)十分困难。此时需要构造逆邻接表才能有效计算入度;

二、封装图结构

在实现过程中采用邻接表的方式来表示边,使用字典类来存储邻接表。

2.1.添加字典类和队列类

首先需要引入之前实现的,之后会用到的字典类和队列类:

    //封装字典类
function Dictionary(){
  //字典属性
  this.items = {}

  //字典操作方法
  //一.在字典中添加键值对
  Dictionary.prototype.set = function(key, value){
    this.items[key] = value
  }

  //二.判断字典中是否有某个key
  Dictionary.pro

今天的文章JavaScript实现图结构分享到此就结束了,感谢您的阅读。

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

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注