广度优先搜索是什么过程（广度优先搜索的过程）

科技前沿 • 2025-04-20 08:27 • 阅读 36

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

最近在校事情不多，趁着还记得就开了个新坑 algorithms，把常用数据结构和算法总结了一下。每个算法都有 README.md 介绍算法的运行流程、GIF 演示、复杂度分析及适用场景；每种数据结构会介绍基本概念、操作和应用场景。

图这种数据结构是网状结构的抽象，现实生活中有很多例子，比如航班路线网络、社交网络等。关于图的节点、边、权值、有向无向和强弱连通性等基础概念可参考第一本书第八章。

对于上方的无向图，有两种常见的表示方法：

对于节点 u 指向节点 v 的边，可以表示为，不直接连接则为0。上图对应的邻接矩阵如下：

上图的矩阵完整描述了图的连接情况。由于是无向图，邻接矩阵相对主对角线是 对称的：意味着，对应到代码实现，是一个二维数组或 map 结构。

对于每个节点，将与之直接连接的节点存储在表结构中，上图对应的邻接表如下：

上图中的箭头可表示有向图，在实现上可使用 slice 或链表存储连接节点。

根据图的 稠密程度 选择存储结构，假设图有 N 个节点 E 条边，若：

使用邻接表存储只连接的节点，节省存储空间；使用邻接矩阵将要存储大量的值，浪费空间。

使用邻接矩阵将十分方便的查询连通性，较少的浪费存储空间。邻接表将查找麻烦。

图有 2 个基本操作：添加节点、连接节点形成边。

讯享网

测试成功：使用邻接表表示上边的无向图

BFS（Breadth First Search）：广度优先搜索，广度指的是从一个节点开始 发散性地遍历 周围节点。从某个节点出发，访问它的所有邻接节点，再从这些节点出发，访问它们未被访问过得邻接节点…直到所有节点访问完毕。

有点类似树的层序遍历，但图存在成环的情形，访问过的节点可能会再次访问，所以需要用一个辅助队列来存放待访问的邻接节点。

讯享网

测试成功：

对于 N 个节点，E 条边的图，节点和每条边都会被遍历到一次。时间复杂度为 O(N + E)

对于发散图，辅助队列最多会存放 N 个节点。空间复杂度为 O(N)

其实对于图的遍历有 2 种：BFS 和 DFS，前者使用辅助队列暂存节点，后者使用栈递归调用。二者各有优劣，比如 BFS 能控制队列长度，不像 DFS 那样不易控制栈的大小，DFS 适用于图和树的先序遍历，将放到树的章节学习。