广度优先搜索和深度优先搜索的基本思想（深度与广度优先搜索）



图
github直达地址 https://github.com/fanshyiis/...

在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。

注意：顶点有时也称为节点或者交点，边有时也称为链接。

一个图可以表示一个社交网络，每一个人就是一个顶点，互相认识的人之间通过边联系。

邻接列表：在邻接列表实现中，每一个顶点会存储一个从它这里开始的边的列表。比如，如果顶点A 有一条边到B、C和D，那么A的列表中会有3条边

邻接列表只描述了指向外部的边。A 有一条边到B，但是B没有边到A，所以 A没有出现在B的邻接列表中。查找两个顶点之间的边或者权重会比较费时，因为遍历邻接列表直到找到为止。

邻接矩阵：在邻接矩阵实现中，由行和列都表示顶点，由两个顶点所决定的矩阵对应元素表示这里两个顶点是否相连、如果相连这个值表示的是相连边的权重。例如，如果从顶点A到顶点B有一条权重为 5.6 的边，那么矩阵中第A行第B列的位置的元素值应该是5.6：

了解了图的基本定义后我们来看下如何用es6的类class思想来实现图类

首先我们先定义两个辅助类

Dictionary 字典类来辅助存贮键值对
Queue 队列类来存贮队列

定义Graph类并且在构造函数里初始化字段
vertices 存储点信息
adjList 存储顶点间的链接关系

addVertex 添加顶点的方法，存贮在数组vertices，并且初始化adjList字典里的值
addEdge 添加单向边 接收两个值 在邻接字典里加上从第一个顶点到第二个的关系

到这 一个基本的类就完成了，我们可以通过测试代码来测试

得到的图

下面我们来定义一个功能来打印图

执行文件 node graph.js

得到结果

好到这就基本完成类的结构了，下面进行图的遍历

广度优先 - 数据结构 队列

先上代码

直到所有顶点探索完

深度优先 - 数据结构 栈

先上代码

深度优先的原则以栈为数据结构

完成探索

具体还有PLus版的深度和广度优先的算法，具体代码奉上

github直达地址 https://github.com/fanshyiis/...

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/rgzn-sdxx/36240.html