算法数据结构——图的遍历之广度优先搜索算法（Breadth First Search）

算法数据结构——图的遍历之广度优先搜索算法（Breadth First Search）

2024-11-01 00:59

广度优先搜索算法（Breadth First Search）：简称为 BFS，又译作宽度优先搜索 / 横向优先搜索。是一种用于遍历或搜索树或图的算法。该算法从根节点开始，沿着树的宽度遍历树或图的节点。如果所有节点均被访问，则算法中止。

广度优先遍历类似于树的层次遍历过程。呈现出一层一层向外扩张的特点。先看到的节点先访问，后看到的节点后访问。遍历到的节点顺序符合「先进先出」的特点，所以广度优先搜索可以通过「队列」来实现。

接下来我们以一个无向图为例，演示一下广度优先搜索的过程。

我们用邻接字典的方式存储无向图结构，对应结构代码如下：

# 定义无向图结构
	graph = {
	"A": ["B", "C"],
	"B": ["A", "C", "D"],
	"C": ["A", "B", "D", "E"],
	"D": ["B", "C", "E", "F"],
	"E": ["C", "D"],
	"F": ["D"]
	}

该无向图对应的邻接字典表示：无向图中有、、、、、共个节点，其中与节点相连的有、两个节点，与节点相连的有、、三个节点，等等。

该无向图的结构如图左所示，其宽度优先搜索的遍历路径如图右所示。

其广度优先搜索的遍历过程如下动图所示。

3.1 基于队列实现的广度优先搜索实现步骤

定义为存储无向图的字典变量，为开始节点，为队列实现的广度优先搜索方法。
定义为标记访问节点的 set 集合变量，为存放节点的队列。
首先将起始节点标记为访问，即。并将其放入队列中，即。
从队列中取出第一个节点。访问节点，并对节点进行相关操作（看具体题目要求）。
遍历与节点相连并构成边的节点。
- 如果没有被访问过（即不在中）：则将节点放入队列中，并标记访问，即，。
重复步骤 4 ~ 5，直到队列为空。

3.2 基于队列实现的广度优先搜索实现代码

4.1 克隆图

4.1.1 题目链接

133. 克隆图 - 力扣（LeetCode）

4.1.2 题目大意

描述：以每个节点的邻接列表形式（二维列表）给定一个无向连通图，其中表示值为的节点的邻接列表，表示值为的节点与值为的节点有一条边。

要求：返回该图的深拷贝。

节点数不超过。
每个节点值 $Node.val$ 都是唯一的，$1 le Node.val le 100$。
无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
由于图是无向的，如果节点是节点的邻居，那么节点也必须是节点的邻居。
图是连通图，你可以从给定节点访问到所有节点。

输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
	输出：[[2,4],[1,3],[2,4],[1,3]]
	解释：
	图中有 4 个节点。
	节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
	节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
	节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
	节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

输入：adjList = [[2],[1]]
	输出：[[2],[1]]

4.1.3 解题思路

使用哈希表来存储原图中被访问过的节点和克隆图中对应节点，键值对为原图被访问过的节点：克隆图中对应节点。使用队列存放节点。
根据起始节点，创建一个新的节点，并将其添加到哈希表中，即。然后将起始节点放入队列中，即。
从队列中取出第一个节点。访问节点。
遍历与节点相连并构成边的节点。
1. 如果没有被访问过（即不在中）：
  1. 则根据创建一个新的节点，并将其添加到哈希表中，即。
  2. 然后将节点放入队列中，即。
重复步骤 3 ~ 4，直到队列为空。
广度优先搜索结束，返回起始节点的克隆节点（即）。

时间复杂度：$O(n)$。其中 $n$ 为图中节点数量。
空间复杂度：$O(n)$。

4.2 岛屿的最大面积

4.2.1 题目链接

695. 岛屿的最大面积 - 力扣（LeetCode）

4.2.2 题目大意

描述：给定一个只包含、元素的二维数组，代表岛屿，代表水。一座岛的面积就是上下左右相邻的所组成的连通块的数目。

要求：计算出最大的岛屿面积。

$m == grid.length$。
$n == grid[i].length$。
$1 le m, n le 50$。
$gridi$ 为或。

输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
	输出：6
	解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
	输入：grid = [[0,0,0,0,0,0,0,0]]
	输出：0

4.2.3 解题思路

使用记录最大岛屿面积。
遍历二维数组的每一个元素，对于每个值为的元素：
1. 将该元素置为。并使用队列存储该节点位置。使用记录当前岛屿面积。
2. 然后从队列中取出第一个节点位置。遍历该节点位置上、下、左、右四个方向上的相邻节点。并将其置为（避免重复搜索）。并将其加入到队列中。并累加当前岛屿面积，即。
3. 不断重复上一步骤，直到队列为空。
4. 更新当前最大岛屿面积，即。

以上就是本篇文章【算法数据结构——图的遍历之广度优先搜索算法（Breadth First Search）】的全部内容了，欢迎阅览！文章地址：http://dfvalve.xrbh.cn/news/8871.html
资讯企业新闻行情企业黄页同类资讯首页网站地图返回首页迅博思语资讯移动站 http://keant.xrbh.cn/ , 查看更多