算法数据结构——图的遍历之广度优先搜索算法(Breadth First Search)
广度优先搜索算法(Breadth First Search):简称为 BFS,又译作宽度优先搜索 / 横向优先搜索。是一种用于遍历或搜索树或图的算法。该算法从根节点开始,沿着树的宽度遍历树或图的节点。如果所有节点均被访问,则算法中止。广度优先遍历类似于树的层次遍历过程。呈现出一层一层向外扩张的特点。先看到的节点先访问,后看到的节点后访问。遍历到的节点顺序符合「先进先出」的特点,所以广度优先搜索可以
1. 广度优先搜索简介
广度优先搜索算法(Breadth First Search):简称为 BFS,又译作宽度优先搜索 / 横向优先搜索。是一种用于遍历或搜索树或图的算法。该算法从根节点开始,沿着树的宽度遍历树或图的节点。如果所有节点均被访问,则算法中止。
广度优先遍历类似于树的层次遍历过程。呈现出一层一层向外扩张的特点。先看到的节点先访问,后看到的节点后访问。遍历到的节点顺序符合「先进先出」的特点,所以广度优先搜索可以通过「队列」来实现。
2. 广度优先搜索过程演示
接下来我们以一个无向图为例,演示一下广度优先搜索的过程。
我们用邻接字典的方式存储无向图结构,对应结构代码如下:
# 定义无向图结构 graph = { "A": ["B", "C"], "B": ["A", "C", "D"], "C": ["A", "B", "D", "E"], "D": ["B", "C", "E", "F"], "E": ["C", "D"], "F": ["D"] }
该无向图对应的邻接字典表示:无向图中有 A
、B
、C
、D
、E
、F
共 6
个节点,其中与 A
节点相连的有 B
、C
两个节点,与 B
节点相连的有 A
、C
、D
三个节点,等等。
该无向图的结构如图左所示,其宽度优先搜索的遍历路径如图右所示。
其广度优先搜索的遍历过程如下动图所示。
3. 基于队列实现的广度优先搜索
3.1 基于队列实现的广度优先搜索实现步骤
-
定义
graph
为存储无向图的字典变量,start
为开始节点,def bfs(graph, start):
为队列实现的广度优先搜索方法。 -
定义
visited
为标记访问节点的 set 集合变量,queue
为存放节点的队列。 -
首先将起始节点标记为访问,即
visited.add(start)
。并将其放入队列queue
中,即queue.append(start)
。 -
从队列中取出第一个节点
node_u
。访问节点node_u
,并对节点进行相关操作(看具体题目要求)。 -
遍历与节点
node_u
相连并构成边的节点node_v
。-
如果
node_v
没有被访问过(即node_v
不在visited
中):则将node_v
节点放入队列中,并标记访问,即q.append(node_v)
,visited.add(node_v)
。
-
-
重复步骤 4 ~ 5,直到队列
queue
为空。
3.2 基于队列实现的广度优先搜索实现代码
import collections
def bfs(graph, start):
visited = set()
queue = collections.deque([])
visited.add(start)
queue.append(start)
while queue:
node_u = queue.popleft()
print(node_u)
for node_v in graph[node_u]:
if node_v not in visited:
visited.add(node_v)
queue.append(node_v)
4. 广度优先搜索应用
4.1 克隆图
4.1.1 题目链接
4.1.2 题目大意
描述:以每个节点的邻接列表形式(二维列表)给定一个无向连通图,其中 adjList[i]
表示值为 i + 1
的节点的邻接列表,adjList[i][j]
表示值为 i + 1
的节点与值为 adjList[i][j]
的节点有一条边。
要求:返回该图的深拷贝。
说明:
-
节点数不超过
100
。 -
每个节点值 $Node.val$ 都是唯一的,$1 \le Node.val \le 100$。
-
无向图是一个简单图,这意味着图中没有重复的边,也没有自环。
-
由于图是无向的,如果节点
p
是节点q
的邻居,那么节点q
也必须是节点p
的邻居。 -
图是连通图,你可以从给定节点访问到所有节点。
示例:
输入: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:广度优先搜索
-
使用哈希表
visited
来存储原图中被访问过的节点和克隆图中对应节点,键值对为 原图被访问过的节点:克隆图中对应节点。使用队列queue
存放节点。 -
根据起始节点,创建一个新的节点,并将其添加到哈希表
visited
中,即visited[node] = Node(node.val, [])
。然后将起始节点放入队列queue
中,即queue.append(node)
。 -
从队列中取出第一个节点
node_u
。访问节点node_u
。 -
遍历与节点
node_u
相连并构成边的节点node_v
。-
如果
node_v
没有被访问过(即node_v
不在visited
中):-
则根据
node_v
创建一个新的节点,并将其添加到哈希表visited
中,即visited[node_v] = Node(node_v.val, [])
。 -
然后将
node_v
节点放入队列queue
中,即queue.append(node_v)
。
-
-
-
重复步骤 3 ~ 4,直到队列
queue
为空。 -
广度优先搜索结束,返回起始节点的克隆节点(即
visited[node]
)。
思路 1:代码
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if not node:
return node
visited = dict()
queue = collections.deque()
visited[node] = Node(node.val, [])
queue.append(node)
while queue:
node_u = queue.popleft()
for node_v in node_u.neighbors:
if node_v not in visited:
visited[node_v] = Node(node_v.val, [])
queue.append(node_v)
visited[node_u].neighbors.append(visited[node_v])
return visited[node]
思路 1:复杂度分析
-
时间复杂度:$O(n)$。其中 $n$ 为图中节点数量。
-
空间复杂度:$O(n)$。
4.2 岛屿的最大面积
4.2.1 题目链接
4.2.2 题目大意
描述:给定一个只包含 0
、1
元素的二维数组,1
代表岛屿,0
代表水。一座岛的面积就是上下左右相邻的 1
所组成的连通块的数目。
要求:计算出最大的岛屿面积。
说明:
-
$m == grid.length$。
-
$n == grid[i].length$。
-
$1 \le m, n \le 50$。
-
$gridi$ 为
0
或1
。
示例:
输入: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:广度优先搜索
-
使用
ans
记录最大岛屿面积。 -
遍历二维数组的每一个元素,对于每个值为
1
的元素:-
将该元素置为
0
。并使用队列q
存储该节点位置。使用temp_ans
记录当前岛屿面积。 -
然后从队列
q
中取出第一个节点位置(i, j)
。遍历该节点位置上、下、左、右四个方向上的相邻节点。并将其置为0
(避免重复搜索)。并将其加入到队列中。并累加当前岛屿面积,即temp_ans += 1
。 -
不断重复上一步骤,直到队列
q
为空。 -
更新当前最大岛屿面积,即
ans = max(ans, temp_ans)
。
-
思路 1:代码
import collections
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
rows, cols = len(grid), len(grid[0])
ans = 0
for i in range(rows):
for j in range(cols):
if grid[i][j] == 1:
grid[i][j] = 0
temp_ans = 1
q = collections.deque([(i, j)])
while q:
i, j = q.popleft()
for direct in directs:
new_i = i + direct[0]
new_j = j + direct[1]
if new_i < 0 or new_i >= rows or new_j < 0 or new_j >= cols or grid[new_i][new_j] == 0:
continue
grid[new_i][new_j] = 0
q.append((new_i, new_j))
temp_ans += 1
ans = max(ans, temp_ans)
return ans
思路 1:复杂度分析
-
时间复杂度:$O(n \times m)$,其中 $m$ 和 $n$ 分别为行数和列数。
-
空间复杂度:$O(n \times m)$。
更多推荐
所有评论(0)