广度优先搜索BFS
定义&基本内容
广度优先是按照层次由近及远的进行搜索,在当前层次所有可及节点都搜索完毕后才会继续往下搜索,其本质就是寻找从起点到终点的最短路程。
树的广度优先搜索
树的广度优先遍历,可以看成是层序遍历。
访问顺序如图:
图的广度优先搜索
有向图:边存在方向的图;
- 有向图中度分为入度(in-degree)和出度(out-degree)
- 入度:表示有多少条边指向这个顶点;
- 出度:表示有多少条边是以这个顶点为起点指向其他节点。
往往被用在最短路径的场景中。
从节点A开始广度优先遍历。
- 步骤1,访问A
- 步骤2,访问A的出边的顶点B
- 步骤3,访问B的出边顶点C/ E /F
- 步骤4,访问E的出边顶点D
- 步骤5,访问F的出边的顶点G
访问步骤:
A - B - C - E - F - D - G
力扣题目实例
200. 岛屿数量
https://leetcode.cn/problems/number-of-islands/description/
深度优先搜索解法:
python算法与数据结构(搜索算法和拓扑排序算法)—深度优先搜索
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def bfs(grid, i, j, rows, cols):
queue = [[i, j]]
while queue:
[i, j] = queue.pop(0)
if 0 <= i <= rows - 1 and 0 <= j <= cols - 1 and grid[i][j] == "1":
grid[i][j] = '0'
queue += [[i+1, j], [i-1, j], [i, j-1], [i, j+1]]
# 获取二维数组的行数和列数
rows = len(grid)
cols = len(grid[0])
res = 0
for i in range(rows):
for j in range(cols):
# 只有确认时岛屿,才会遍历
if grid[i][j] == '0':
continue
res += 1
bfs(grid, i, j, rows, cols)
return res