图论大总结
图论基础
98. 所有可达路径
result = []
path = []
def dfs(graph,x,n):
if x == n:
result.append(path[:])
return
for i in range(1,n+1):
if graph[x][i] == 1:
path.append(i)
dfs(graph,i,n)
path.pop()
def main():
n,m = map(int,input().split())
# 邻接矩阵
graph = [[0]*(n+1) for _ in range(n+1)]
for _ in range(m):
s,t = map(int,input().split())
graph[s][t] = 1
path.append(1)
dfs(graph,1,n)
if len(result) == 0:
print(-1)
for x in result:
print(' '.join(map(str,x)))
if __name__ == "__main__":
main()
岛屿问题
200. 岛屿数量
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
res = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == "1":
res += 1
self.dfs(grid,i,j)
return res
def dfs(self,grid,x,y):
# 判断(x,y)是否在网格范围内
if not (x >= 0 and y >=0 and x <len(grid) and y<len(grid[0])):
return
if grid[x][y] != "1": # 海洋格子以及遍历过的陆地格子直接返回
return
grid[x][y] = "2"
self.dfs(grid,x-1,y) # 上
self.dfs(grid,x+1,y) # 下
self.dfs(grid,x,y-1) # 左
self.dfs(grid,x,y+1) # 右
695. 岛屿的最大面积
class Solution:
def dfs(self,grid,x,y,i):
if not (x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0])):
return 0
if grid[x][y] == 0:
return 0
grid[x][y] = i
s1 = self.dfs(grid,x-1,y,i)
s2 = self.dfs(grid,x+1,y,i)
s3 = self.dfs(grid,x,y-1,i)
s4 = self.dfs(grid,x,y+1,i)
return 1 + s1 + s2 + s3 + s4
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
maxarea = 0
num = 2
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
res = self.dfs(grid,i,j,num)
maxarea = max(maxarea,res)
num += 1
return maxarea
827. 最大人工岛
class Solution:
def dfs(self,grid,x,y,i):
if not (x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0])):
return 0
# grid == 0 : 海洋 grid == 1 : 陆地但没被遍历过 grid == i 陆地但遍历过
if grid[x][y] != 1:
return 0
grid[x][y] = i
s1 = self.dfs(grid,x-1,y,i)
s2 = self.dfs(grid,x+1,y,i)
s3 = self.dfs(grid,x,y-1,i)
s4 = self.dfs(grid,x,y+1,i)
return 1 + s1 + s2 + s3 + s4
def dfs2(self,grid,x,y,island_area):
if not (x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0])):
return 0
# grid == 0 : 海洋(没被遍历) grid == 1 : 海洋(被遍历) grid == i 陆地面积
if grid[x][y] == 1:
return 0
if grid[x][y] != 0:
return island_area[grid[x][y]]
grid[x][y] = 1
s1 = self.dfs2(grid,x-1,y,island_area)
s2 = self.dfs2(grid,x+1,y,island_area)
s3 = self.dfs2(grid,x,y-1,island_area)
s4 = self.dfs2(grid,x,y+1,island_area)
s = set(grid[x-1][y],grid[x+1][y],grid[x][y-1],grid[x][y+1])
return s1 + s2 + s3 + s4
def largestIsland(self, grid: List[List[int]]) -> int:
island_area = {}
num = 2
res = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
area = self.dfs(grid,i,j,num)
island_area[num] = area
num += 1
print(grid)
print(island_area)
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 0:
sea_area = self.dfs2(grid,i,j,island_area)
res = max(res,1+sea_area)
return res
原文地址:https://blog.csdn.net/qq_43403653/article/details/142732535
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!