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