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

科技前沿 • 2025-04-22 21:51 • 阅读 38

大家好，我是讯享网，很高兴认识大家。

图
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：

往这个图中添加顶点的成本非常昂贵，因为新的矩阵结果必须重新按照新的行/列创建，然后将已有的数据复制到新的矩阵中。
所以使用哪一个呢？大多数时候，选择邻接列表是正确的。下面是两种实现方法更详细的比较。
假设 V 表示图中顶点的个数，E 表示边的个数。

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

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

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

讯享网

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

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

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

讯享网

得到的图

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

执行文件 node graph.js

得到结果

讯享网

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

广度优先 - 数据结构队列

先上代码

基本思想如下
1.初始化各个顶点的颜色（白色 - 未访问；灰色 - 已发现；黑色 - 已经探索完）
2.初始化一个队列
3.首先队列入顶点 v
4.如果队列不会空，则取队列第一个进行探索
5.探索过程中获取当前顶点的所有邻接顶点，并推进队列
6.完成5后，标记当前为黑色

图示例
A 探索队列入 B - C - D
完成 A探索
出B 探索B 队列再入 E - F 当前 CDEF
完成 B探索
出C 探索队列再入 G 当前DEFG
。。。

直到所有顶点探索完

深度优先 - 数据结构栈

先上代码

讯享网

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

基本思想如下
1.初始化各个顶点的颜色（白色 - 未访问；灰色 - 已发现；黑色 - 已经探索完）
2.对顶点进行遍历并进行dfsVisit函数探索
3.优先进行最新探索的边进行深度探索，完成后标记探索完成

基本步骤如下
探索A
发现BCD
探索B
发现EF
探索E
发现I
探索I，完毕标记I为以探索
回到上个分支遍历接着执行探索F
完成
标记F为以探索
。。。
直到返回到顶点A

完成探索

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

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