图论

图论部分推荐 acm 模式，因为图的输入处理不一样

DFS，类似二叉树的递归遍历
BFS，类似二叉树的层次遍历

leetcode.cn/problems/implement-trie-prefix-tree/description/?envType=study-plan-v2&envId=top-100-liked" rel="nofollow">208. 实现 Trie (前缀树)

数据结构大概如下：

• 可以看成是 二十六叉树 （因为26个小写字母）
  

class Node:def __init__(self):self.son = {}self.end = False  # end=True, 表示当前结点已经构成一个单词class Trie:def __init__(self):self.root = Node()def insert(self, word: str) -> None:cur = self.rootfor c in word:if c not in cur.son:cur.son[c] = Node()cur = cur.son[c]cur.end = Truedef find(self, word: str) -> int:cur = self.rootfor c in word:if c not in cur.son:return 0cur = cur.son[c]return 2 if cur.end else 1def search(self, word: str) -> bool:return self.find(word) == 2def startsWith(self, prefix: str) -> bool:return self.find(prefix) != 0

DFS

（1）leetcode.cn/problems/number-of-islands/description/?envType=study-plan-v2&envId=top-100-liked" rel="nofollow">200. 岛屿数量

方法一：DFS

class Solution:def numIslands(self, grid: List[List[str]]) -> int:dx = [0,-1,0,1]dy = [-1,0,1,0]def dfs(i, j):if (not 0 <= i < m) or (not 0 <= j < n) or grid[i][j] == '0':returngrid[i][j] = '0'for idx in range(4):x = i + dx[idx]y = j + dy[idx]dfs(x,y)m = len(grid)n = len(grid[0])ans = 0 for i in range(m):for j in range(n):if grid[i][j] == "1":dfs(i,j)  # 把整个岛都标记ans += 1return ans

ACM 代码模式：99. 岛屿数量

读取每一行输入map(int, input().split())

• input().split()，将输入的行，按照空格切分每个元素，返回一个list
• map(int, input().split())，将 list 中每个元素转化为指定的 int类型，返回一个可迭代的对象

例如输入1 2 3 4

• input().split()，得到[‘1’, ‘2’, ‘3’, ‘4’]
• list(map(int, input().split()))，[1, 2, 3, 4]

dx = [-1,0,1,0]
dy = [0,-1,0,1]def dfs(i, j):if not (0<=i<n) or not (0<=j<m) or grid[i][j]==0:return grid[i][j] = 0for idx in range(4):x = dx[idx] + iy = dy[idx] + jdfs(x, y)if __name__ == '__main__':n,m = map(int, input().split())grid = []for i in range(n):grid.append(list(map(int, input().split())))# visited = [ [False] * m for _ in range(n) ]ans = 0for i in range(n):for j in range(m):if grid[i][j] == 1:dfs(i, j)ans += 1print(ans)

（2）100. 岛屿的最大面积

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
s = 0def dfs(i, j):if not (0 <= i < n) or not (0 <= j < m) or grid[i][j] == 0:returnglobal ss += 1grid[i][j] = 0for idx in range(4):x = dx[idx] + iy = dy[idx] + jdfs(x, y)if __name__ == '__main__':n, m = map(int, input().split())grid = []for i in range(n):grid.append(list(map(int, input().split())))ans = 0for i in range(n):for j in range(m):if grid[i][j] == 1:s = 0dfs(i, j)ans = max(ans, s)print(ans)

（3）101. 孤岛的总面积

dx = [-1,0,1,0]
dy = [0,-1,0,1]
s = 0def dfs(i,j):if not (0<=i<n) or not (0<=j<m) or grid[i][j] == 0:returnglobal ss += 1grid[i][j] = 0for idx in range(4):x = dx[idx] + iy = dy[idx] + jdfs(x,y)if __name__ == '__main__':n, m = map(int, input().split())grid = []for i in range(n):grid.append(list(map(int, input().split())))# 将四周贴边的非孤岛区域转为水# 遍历第一列和最后一列for i in range(n):if grid[i][0] == 1:dfs(i,0)elif grid[i][m-1] == 1:dfs(i,m-1)# 遍历第一行和最后一行for j in range(m):if grid[0][j] == 1:dfs(0,j)elif grid[n-1][j] == 1:dfs(n-1,j)# 计算孤岛面积s = 0for i in range(n):for j in range(m):if grid[i][j] == 1:dfs(i,j)print(s)

（4）102. 沉没孤岛

dx = [-1,0,1,0]
dy = [0,-1,0,1]def dfs(i,j):if not (0 <= i < n) or not(0 <= j < m) or grid[i][j] != 1:return grid[i][j] = 2for k in range(4):x = dx[k] + iy = dy[k] + jdfs(x,y)if __name__ == '__main__':n,m = map(int, input().split())grid = []for _ in range(n):grid.append(list(map(int, input().split())))for i in range(n):if grid[i][0] == 1:dfs(i, 0)if grid[i][m-1] == 1:dfs(i, m-1)for j in range(m):if grid[0][j] == 1:dfs(0,j)if grid[n-1][j] == 1:dfs(n-1, j)for i in range(n):for j in range(m):if grid[i][j] == 1:grid[i][j] = 0elif grid[i][j] == 2:grid[i][j] = 1print(' '.join(map(str, grid[i])))

BFS

（1）leetcode.cn/problems/rotting-oranges/description/?envType=study-plan-v2&envId=top-100-liked" rel="nofollow">994. 腐烂的橘子

使用 BFS 是为了实现，同一个时间，当前所有腐烂的橘子同时腐烂周围

from collections import deque
class Solution:def orangesRotting(self, grid: List[List[int]]) -> int:n, m = len(grid), len(grid[0])q = deque()count = 0  # 新鲜橘子数for i in range(n):for j in range(m):if grid[i][j] == 1:count += 1elif grid[i][j] == 2:q.append((i,j))dx = [-1,0,1,0]dy = [0,-1,0,1]round = 0  # 分钟数while count > 0 and len(q) > 0:round += 1cur = len(q)  # 这一轮有多少个腐烂的橘子一起腐烂周围for _ in range(cur):i,j = q.popleft()for idx in range(4):x = dx[idx] + iy = dy[idx] + jif (0<=x<n) and (0<=y<m) and grid[x][y] == 1:grid[x][y] = 2count -= 1q.append((x,y))if count > 0:return -1else:return round

（2）leetcode.cn/problems/course-schedule/description/?envType=study-plan-v2&envId=top-100-liked" rel="nofollow">207. 课程表

1. 每次只能修当前可以修的课程——入度为0的课程
2. 修完一轮后，再修可以休的课程——入度变为0的课程
3. 所以我们需要记录每个课程的入度，
4. 然后需要邻接矩阵来关联课程之间的关系，从而更新入度
   

from collections import deque
class Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:indegree = [0] * numCourses  # 每个课程的入度(即先修课程有几门)adj = defaultdict(list) # key为当前课，value为它的后续课程,用列表存# 初始化入度和邻接表for cur,pre in prerequisites:indegree[cur] += 1adj[pre].append(cur)# 把入度为0的入队列q = deque()for i in range(numCourses):if indegree[i] == 0:q.append(i)while q:n = len(q)for i in range(n):pre = q.popleft()numCourses -= 1# 遍历课程pre的邻接表：它的后续课程for cur in adj[pre]:# 将后续课程的入度 -1indegree[cur] -= 1if indegree[cur] == 0:q.append(cur)return numCourses == 0