来源于leetcode题库102,200,207
BFS解题模版
- 模版来自于大佬负雪明烛
#BFS模版
# (1)不需要确定当前遍历到哪一层
while queue 不空：
cur = queue.pop()
for 节点 in cur的所有相邻节点：
if 该节点有效且未访问过：
queue.push(该节点)
# (2)需要确定当前遍历到哪一层了
'''
level表示当前遍历到二叉树中的哪一层了，
也可以理解为在一个图中，现在已经走了多少步了
'''
level = 0
while queue 不空：
size = queue.size()
while (size --) {
cur = queue.pop()
for 节点 in cur的所有相邻节点：
if 该节点有效且未被访问过：
queue.push(该节点)
}
level ++;
102.二叉树的层序遍历
- 题目描述
- 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
- 示例
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
- 题解
for i in range(10):
循环体中可以使用i
for _ in range(10):
用下划线则仅用于控制循环次数，后边不会用到该变量
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
#创建队列并将根节点加入队列
queue = collections.deque()
queue.append(root)
res = []
#套用模板
while queue:
size = len(queue)
level = []
for _ in range(size):
cur = queue.popleft()
if not cur:
continue
# 每一层的值
level.append(cur.val)
# 将该节点的左右子节点加入队列
queue.append(cur.left)
queue.append(cur.right)
if level:#将值放进结果中
res.append(level)
return res
200.岛屿数量
- 题目描述
- 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
-
示例
image.png 题解
来自大佬莲子熊猫
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
count = 0
for row in range(len(grid)):#行
for col in range(len(grid[0])):#列
if grid[row][col] == '1': # 发现陆地
count += 1 # 结果加1
grid[row][col] = '0' # 将其转为 ‘0’ 代表已经访问过
# 对发现的陆地进行扩张即执行 BFS，将与其相邻的陆地都标记为已访问
# BFS 模板
land_positions = collections.deque()
land_positions.append([row, col])
while len(land_positions) > 0:
x, y = land_positions.popleft()
# 进行四个方向的扩张
for new_x, new_y in [[x, y + 1], [x, y - 1], [x + 1, y], [x - 1, y]]:
# 判断有效性
if 0 <= new_x < len(grid) and 0 <= new_y < len(grid[0]) and grid[new_x][new_y] == '1':
grid[new_x][new_y] = '0' # 因为可由 BFS 访问到，代表同属一块岛，将其置 ‘0’ 代表已访问过
land_positions.append([new_x, new_y])
return count
207.课程表
- 题目描述：
- 你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
- 你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
- 示例：
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
- 题解：
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
'''
有向无圈图DAG，如果构成环路是不成立的
通过拓扑排序判断是否是DAG：
对DAG对顶点进行排序，使得每一条有向边(u,v),均符合y比v先出现
DFS解法
借助一个列表flags用于判断每个节点的状态：
未被访问，i==0
已被其他节点启动的DFS访问，i==-1
已被当前节点启动的DFS访问，i==1
对numCourses个节点依次执行DFS，判断是否有环：
当flags[i]==-1,被其他节点访问过，返回True
当flags[i]==1,已在本轮搜索中访问过，即有环，返回False
将当前节点i对应flags[i]置为1，表示本轮访问过
递归访问当前节点i的所有邻接节点j，发现环返回False
当前节点的所有邻接节点也被遍历，则当前节点置为-1，返回True
如果整个图DFS结束都没发现环，返回True
'''
def dfs(i,adjacency,flags):
#终止条件
if flags[i] == -1:
return True
if flags[i] == 1:
return False
#当前点置为1
flags[i] = 1
#对当前节点对所有邻接点进行dfs
for j in adjacency[i]:
if not dfs(j,adjacency,flags):
return False
#没有环则当前节点置为-1，下次不需要再进行dfs了，返回True
flags[i] = -1
return True
#
adjacency = [[] for _ in range(numCourses)]
flags = [0 for _ in range(numCourses)]
for cur,pre in prerequisites:
adjacency[pre].append(cur)
#对所有节点进行dfs
for i in range(numCourses):
if not dfs(i,adjacency,flags):
return False
return True
'''
BFS解法：
统计课程安排图中每个节点的入度，生成入度表indegrees
借助一个队列queue，将所有入度为0的节点入队
当queue不为空，依次队首节点出队，在课程安排图中删除此节点pre
并不是真正从邻接表删除，而是此节点对应所有邻接节点cur-1
当入度-1后邻接节点cur的入度为0，说明cur的前驱节点已经被删除，此时cur入队
在每次pre出队时，执行numCourses--
若课程安排图是DAG，则所有节点都出队入队过
如图中存在环，则一定有节点的入度始终不为0
拓扑排序出队次数等于课程个数，返回numCourses==0可以判断是否成功
'''
#入度表
indegrees = [0 for _ in range(numCourses)]
#课程的依赖
adjacency = [[] for _ in range(numCourses)]
queue = collections.deque()
# 入度表记录所有节点的入度，
for cur,pre in prerequisites:
indegrees[cur] += 1
adjacency[pre].append(cur)
#入度不为0的加入队列
for i in range(len(indegrees)):
if not indegrees[i]:
queue.append(i)
#BFS
while queue:
#取出队首数据
pre = queue.popleft()
numCourses -= 1
#遍历队首的所有邻接元素
for cur in adjacency[pre]:
indegrees[cur] -= 1
#如果邻接元素入度-1后还不为0，则将其加入队列
if not indegrees[cur]:
queue.append(cur)
return numCourses == 0
