广度优先搜索算法（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"]
}该无向图的结构如图左所示，图右为宽度优先搜索的遍历路径。
其对应的动态演示图如下所示。
graph为存储无向图的字典变量，start为开始节点。- 然后定义
visited为标记访问节点的 set 集合变量。定义q为存放节点的队列。 - 首先将起始节点放入队列
q中，即q.put(start)。并将其标记为访问，即visited.add(start)。 - 从队列中取出第一个节点
node_u。访问节点node_u，并对节点进行相关操作（看具体题目要求）。 - 遍历与节点
node_u相连并构成边的节点node_v。- 如果
node_v没有被访问过，则将node_v节点放入队列中，并标记访问，即q.append(node_v)，visited.add(node_v)。
- 如果
- 重复步骤 4 ~ 5，直到
q为空。
import collections
def bfs(graph, start):
visited = set(start)
q = collections.deque([start])
while q:
node_u = q.popleft()
print(node_u)
for node_v in graph[node_u]:
if node_v not in visited:
visited.add(node_v)
q.append(node_v)给定 n 个节点（编号从 0 到 n - 1）的图的无向边列表 edges，其中 edges[i] = [u, v] 表示节点 u 和节点 v 之间有一条无向边。
要求：计算该无向图中连通分量的数量。
先来看一下图论中相关的名次解释。
- 连通图：在无向图中，如果可以从顶点
$v_i$ 到达$v_j$ ，则称$v_i$ 和$v_j$ 连通。如果图中任意两个顶点之间都连通，则称该图为连通图。 - 无向图的连通分量：如果该图为连通图，则连通分量为本身；否则将无向图中的极大连通子图称为连通分量，每个连通分量都是一个连通图。
- 无向图的连通分量个数：无向图的极大连通子图的个数。
接下来我们来解决这道题。
由于题目给定的是无向边列表。我们先将其转变为邻接表的形式。然后使用广度优先搜索计算联通分量的个数。具体做法如下：
-
使用变量
count记录连通分量个数。使用集合变量visited记录访问过的节点，使用邻接表graph记录图结构。 -
从
0开始，依次遍历n个节点。 -
如果第
i个节点未访问过：- 将其添加到
visited中。 - 并且连通分量个数累加，即
count += 1。 - 定义一个队列
q，将第i个节点加入到队列中。 - 从队列中取出第一个节点，遍历与其链接的节点，并将未遍历过的节点加入到队列
q和visited中。 - 直到队列为空，则继续向后遍历。
- 将其添加到
-
最后输出连通分量数目
count。
import collections
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
count = 0
visited = set()
graph = [[] for _ in range(n)]
for x, y in edges:
graph[x].append(y)
graph[y].append(x)
for i in range(n):
if i not in visited:
visited.add(i)
count += 1
q = collections.deque([i])
while q:
node_u = q.popleft()
for node_v in graph[node_u]:
if node_v not in visited:
visited.add(node_v)
q.append(node_v)
return count给定一个只包含 0、1 元素的二维数组 grid，其中 1 代表岛屿，0 代表水。一座岛的面积就是上下左右相邻的 1 所组成的连通块的数目。
要求：计算出最大的岛屿面积。
示例 ：
图中最大的岛屿面积为 6。
使用广度优先搜索方法。具体做法如下：
- 使用
ans记录最大岛屿面积。 - 遍历二维数组的每一个元素，对于每个值为
1的元素：- 将该元素置为
0。并使用队列q存储该节点位置。使用temp_ans记录当前岛屿面积。 - 然后从队列
q中取出第一个节点位置(i, j)。遍历该节点位置上、下、左、右四个方向上的相邻节点。并将其置为0（避免重复搜索）。并将其加入到队列中。并累加当前岛屿面积，即temp_ans += 1。 - 不断重复上一步骤，直到队列
q为空。 - 更新当前最大岛屿面积，即
ans = max(ans, temp_ans)。
- 将该元素置为
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