Day9，Hot100（图论）
图论图论部分保举 acm 模式，由于图的输入处置惩罚不一样
DFS，雷同二叉树的递归遍历
BFS，雷同二叉树的层次遍历
208. 实现 Trie (前缀树)
数据结构大概如下：
[*]可以当作是 二十六叉树 （由于26个小写字母）
https://i-blog.csdnimg.cn/direct/e67acf88de3646f3a58110121fdb3378.png
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.root
for c in word:
if c not in cur.son:
cur.son = Node()
cur = cur.son
cur.end = True
def find(self, word: str) -> int:
cur = self.root
for c in word:
if c not in cur.son:
return 0
cur = cur.son
return 2 if cur.end else 1
def search(self, word: str) -> bool:
return self.find(word) == 2
def startsWith(self, prefix: str) -> bool:
return self.find(prefix) != 0
DFS
（1）200. 岛屿数量
https://i-blog.csdnimg.cn/direct/e5f7dd087cf64887bb28ca3380fce54f.png 方法一：DFS
class Solution:
def numIslands(self, grid: List]) -> int:
dx =
dy = [-1,0,1,0]
def dfs(i, j):
if (not 0 <= i < m) or (not 0 <= j < n) or grid == '0':
return
grid = '0'
for idx in range(4):
x = i + dx
y = j + dy
dfs(x,y)
m = len(grid)
n = len(grid)
ans = 0
for i in range(m):
for j in range(n):
if grid == "1":
dfs(i,j)# 把整个岛都标记
ans += 1
return ans
ACM 代码模式：99. 岛屿数量
https://i-blog.csdnimg.cn/direct/e154e3b6d22048a29c2a1df54a027c1e.png
读取每一行输入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()))，
dx = [-1,0,1,0]
dy =
def dfs(i, j):
if not (0<=i<n) or not (0<=j<m) or grid==0:
return
grid = 0
for idx in range(4):
x = dx + i
y = dy + j
dfs(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 = [ * m for _ in range(n) ]
ans = 0
for i in range(n):
for j in range(m):
if grid == 1:
dfs(i, j)
ans += 1
print(ans)
（2）100. 岛屿的最大面积
https://i-blog.csdnimg.cn/direct/892c16831fca40ee88ad86c6547b6b84.png
dx = [-1, 0, 1, 0]
dy =
s = 0
def dfs(i, j):
if not (0 <= i < n) or not (0 <= j < m) or grid == 0:
return
global s
s += 1
grid = 0
for idx in range(4):
x = dx + i
y = dy + j
dfs(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 = 0
for i in range(n):
for j in range(m):
if grid == 1:
s = 0
dfs(i, j)
ans = max(ans, s)
print(ans)
（3）101. 孤岛的总面积
https://i-blog.csdnimg.cn/direct/5b63902a14bb4827a6476cdb64e04a25.png
https://i-blog.csdnimg.cn/direct/823fbb336fec40eca6a0bd9f35fd0a32.png
步骤
[*]首先把四周靠边界的岛屿都设为 0
[*]然后遍历剩余的孤岛面积
dx = [-1,0,1,0]
dy =
s = 0
def dfs(i,j):
if not (0<=i<n) or not (0<=j<m) or grid == 0:
return
global s
s += 1
grid = 0
for idx in range(4):
x = dx + i
y = dy + j
dfs(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 == 1:
dfs(i,0)
elif grid == 1:
dfs(i,m-1)
# 遍历第一行和最后一行
for j in range(m):
if grid == 1:
dfs(0,j)
elif grid == 1:
dfs(n-1,j)
# 计算孤岛面积
s = 0
for i in range(n):
for j in range(m):
if grid == 1:
dfs(i,j)
print(s)
（4）102. 沉没孤岛
https://i-blog.csdnimg.cn/direct/5a3066adb5cf4307afe519abce26e9a6.png
[*]把靠四周的非孤岛标记为2
[*]接着把剩余的1(孤岛)，标记为0
[*]末了把2修改回1
dx = [-1,0,1,0]
dy =
def dfs(i,j):
if not (0 <= i < n) or not(0 <= j < m) or grid != 1:
return
grid = 2
for k in range(4):
x = dx + i
y = dy + j
dfs(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 == 1:
dfs(i, 0)
if grid == 1:
dfs(i, m-1)
for j in range(m):
if grid == 1:
dfs(0,j)
if grid == 1:
dfs(n-1, j)
for i in range(n):
for j in range(m):
if grid == 1:
grid = 0
elif grid == 2:
grid = 1
print(' '.join(map(str, grid)))
BFS
（1）994. 腐烂的橘子
使用 BFS 是为了实现，同一个时间，当前所有腐烂的橘子同时腐烂周围
from collections import deque
class Solution:
def orangesRotting(self, grid: List]) -> int:
n, m = len(grid), len(grid)
q = deque()
count = 0# 新鲜橘子数
for i in range(n):
for j in range(m):
if grid == 1:
count += 1
elif grid == 2:
q.append((i,j))
dx = [-1,0,1,0]
dy =
round = 0# 分钟数
while count > 0 and len(q) > 0:
round += 1
cur = len(q)# 这一轮有多少个腐烂的橘子一起腐烂周围
for _ in range(cur):
i,j = q.popleft()
for idx in range(4):
x = dx + i
y = dy + j
if (0<=x<n) and (0<=y<m) and grid == 1:
grid = 2
count -= 1
q.append((x,y))
if count > 0:
return -1
else:
return round
（2）207. 课程表
https://i-blog.csdnimg.cn/direct/ab9dd8491a5f4d48b41f56e05be16888.png
[*]每次只能修当前可以修的课程——入度为0的课程
[*]修完一轮后，再修可以休的课程——入度变为0的课程
[*]以是我们必要记录每个课程的入度，
[*]然后必要毗邻矩阵来关联课程之间的关系，从而更新入度
https://i-blog.csdnimg.cn/direct/4a6917b399a64b4c8cedf57fc5992aad.png
from collections import deque
class Solution:
def canFinish(self, numCourses: int, prerequisites: List]) -> bool:
indegree = * numCourses# 每个课程的入度(即先修课程有几门)
adj = defaultdict(list) # key为当前课，value为它的后续课程,用列表存
# 初始化入度和邻接表
for cur,pre in prerequisites:
indegree += 1
adj.append(cur)
# 把入度为0的入队列
q = deque()
for i in range(numCourses):
if indegree == 0:
q.append(i)
while q:
n = len(q)
for i in range(n):
pre = q.popleft()
numCourses -= 1
# 遍历课程pre的邻接表：它的后续课程
for cur in adj:
# 将后续课程的入度 -1
indegree -= 1
if indegree == 0:
q.append(cur)
return numCourses == 0
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]