图论¶
简介¶
需要注意的点¶
- 在深度优先搜索的时候数组的处理需要尤其注意,因为python中数组是可以在函数传递过程中被改变的,所以如果要复制数组的内容往往需要使用深拷贝arr[:];
题目¶
797. 所有可能的路径¶
题解:
-
本题是深度优先搜索或广度优先搜索在图中的典型题目
-
首先考虑深度优先搜索DFS,递归终止条件是搜索到最后一个节点,在搜索过程中遍历当前节点所有下一届点并加入路径中,然后进行递归并回溯。
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
n = len(graph)
path = [0]
ans = []
def dfs():
if path[-1] == n - 1:
ans.append(list(path))
for nxt in graph[path[-1]]:
path.append(nxt)
dfs()
path.pop()
dfs()
return ans
- 对于广度优先搜索BFS,处理方式和二叉树的层序遍历类似,利用列表或者队列保存遍历过的路径
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
n = len(graph)
q = deque([[0]])
ans = []
while q:
path = q.popleft()
if path[-1] == n - 1:
ans.append(path)
for nxt in graph[path[-1]]:
q.append(path + [nxt])
return ans
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
n = len(graph)
q = [[0]]
ans = []
while q:
path = q.pop()
if path[-1] == n - 1:
ans.append(path)
for nxt in graph[path[-1]]:
q.append(path + [nxt])
return ans
200. 岛屿数量¶
题解:
-
每当发现一个岛屿时,将与其相连的其他陆地找出并把岛屿数量加一即可,因此可以采用DFS或者BFS求解
-
采用DFS时
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
row, col, res = len(grid), len(grid[0]), 0
def dfs(x, y):
grid[x][y] = '0'
for c in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
nx, ny = x + c[0], y + c[1]
if 0 <= nx < row and 0 <= ny < col and grid[nx][ny] == '1':
dfs(nx, ny)
for i in range(row):
for j in range(col):
if grid[i][j] == '1':
dfs(i, j)
res += 1
return res
- 采用BFS时
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
row, col, res = len(grid), len(grid[0]), 0
def bfs(i, j):
queue = deque([i, j])
grid[i][j] = "0"
while queue:
x, y = queue.popleft()
for c in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
nx, ny = x + c[0], y + c[1]
if 0 <= nx < row and 0 <= ny < col and grid[nx][ny] == "1":
grid[nx][ny] = "0"
queue.append([nx, ny]
for i in range(row):
for j in range(col):
if grid[i][j] == "1":
bfs(i, j)
res += 1
return res
695. 岛屿的最大面积¶
题解:
- DFS:当dfs函数需要计数时,一种方式是定义全局变量累加,==另一种方式是将dfs函数的返回值做为计数==
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
row, col, ans = len(grid), len(grid[0]), 0
def dfs(i, j):
grid[i][j] = 0
res = 1
for c in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
nx, ny = i + c[0], j + c[1]
if 0 <= nx < row and 0 <= ny < col and grid[nx][ny] == 1:
res += dfs(nx, ny) # 这里的计数方式需要注意
return res
for i in range(row):
for j in range(col):
if grid[i][j] == 1:
ans = max(ans, dfs(i, j))
return ans
- BFS:bfs中计数则相对简单
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
def bfs(i, j):
queue = [(i, j)]
grid[i][j] = 0
area = 1
while queue:
x, y = queue.pop()
for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny]:
grid[nx][ny] = 0
area += 1
queue.append((nx, ny))
return area
res = 0
for i in range(m):
for j in range(n):
if grid[i][j]:
res = max(res, bfs(i, j))
return res
1010. 飞地的数量¶
题解:
本题关键点在于理解题意,题目需要找出不包含边界点的岛屿的面积,因此可以先对四条边进行搜索,将包含边界点的岛屿全部变为0,然后统计剩下的岛屿数量即可
- DFS
class Solution:
def numEnclaves(self, grid: List[List[int]]) -> int:
row, col, res = len(grid), len(grid[0]), 0
def dfs(x, y):
grid[x][y] = 0
for dir in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
nx, ny = x + dir[0], y + dir[1]
if 0 <= nx < row and 0 <= ny < col and grid[nx][ny]:
dfs(nx, ny)
for i in range(row):
if grid[i][0]:
dfs(i, 0)
if grid[i][col - 1]:
dfs(i, col - 1)
for i in range(1, col - 1):
if grid[0][i]:
dfs(0, i)
if grid[row - 1][i]:
dfs(row - 1, i)
for i in range(row):
for j in range(col):
if grid[i][j] == 1:
res += 1
return res
- BFS
class Solution:
def numEnclaves(self, grid: List[List[int]]) -> int:
row, col, res = len(grid), len(grid[0]), 0
def bfs(x, y):
que = deque([[x, y]])
grid[x][y] = 0
while que:
i, j = que.popleft()
for dir in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
nx, ny = i + dir[0], j + dir[1]
if 0 <= nx < row and 0 <= ny < col and grid[nx][ny]:
grid[nx][ny] = 0
que.append([nx, ny])
for i in range(row):
if grid[i][0]:
bfs(i, 0)
if grid[i][col - 1]:
bfs(i, col - 1)
for i in range(1, col - 1):
if grid[0][i]:
bfs(0, i)
if grid[row - 1][i]:
bfs(row - 1, i)
for i in range(row):
for j in range(col):
if grid[i][j] == 1:
res += 1
return res
¶
题解:
本题与飞地的数量类似,只不过本题需要把飞地找出来并改变数值,因此仍然可以按照飞地的数量的解法,先对四周的陆地进行处理
- DFS
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
row, col = len(board), len(board[0])
def dfs(x, y):
board[x][y] = 'Y'
for dir in [[0, 1], [0, -1], [-1, 0], [1, 0]]:
nx, ny = x + dir[0], y + dir[1]
if 0 <= nx < row and 0 <= ny < col and board[nx][ny] == 'O':
dfs(nx, ny)
for i in range(row):
if board[i][0] == 'O':
dfs(i, 0)
if board[i][col - 1] == 'O':
dfs(i, col - 1)
for j in range(1, col - 1):
if board[0][j] == 'O':
dfs(0, j)
if board[row - 1][j] == 'O':
dfs(row - 1, j)
for i in range(row):
for j in range(col):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == 'Y':
board[i][j] = 'O'
- BFS
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
row, col = len(board), len(board[0])
def bfs(x, y):
board[x][y] = 'Y'
que = deque([[x, y]])
while que:
i, j = que.popleft()
for dir in [[0, 1], [0, -1], [-1, 0], [1, 0]]:
nx, ny = i + dir[0], j + dir[1]
if 0 <= nx < row and 0 <= ny < col and board[nx][ny] == 'O':
board[nx][ny] = 'Y'
que.append([nx, ny])
for i in range(row):
if board[i][0] == 'O':
bfs(i, 0)
if board[i][col - 1] == 'O':
bfs(i, col - 1)
for j in range(1, col - 1):
if board[0][j] == 'O':
bfs(0, j)
if board[row - 1][j] == 'O':
bfs(row - 1, j)
for i in range(row):
for j in range(col):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == 'Y':
board[i][j] = 'O'
417. 太平洋大西洋水流问题¶
题解:
本题仍然需要从边界出发,遍历边界附近更高的点。只是这道题的边界有两种情况,因此需要定义两个状态矩阵分别对应太平洋和大西洋边界的情况
- DFS
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
row, col = len(heights), len(heights[0])
def dfs(x, y, arr):
arr[x][y] = 1
for dir in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
nx, ny = x + dir[0], y + dir[1]
if (0 <= nx < row and 0 <= ny < col and heights[nx][ny] >= heights[x][y]
and not arr[nx][ny]):
dfs(nx, ny, arr)
pacific = [[0] * col for _ in range(row)]
atlantic = [[0] * col for _ in range(row)]
for i in range(col):
dfs(0, i, pacific)
dfs(row - 1, i, atlantic)
for i in range(row):
dfs(i, 0, pacific)
dfs(i, col - 1, atlantic)
return [[i, j] for i in range(row) for j in range(col) if pacific[i][j] and atlantic[i][j]]
- BFS
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
row, col = len(heights), len(heights[0])
def bfs(i, j, arr):
arr[i][j] = 1
que = deque([[i, j]])
while que:
x, y = que.popleft()
for dir in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
nx, ny = x + dir[0], y + dir[1]
if (0 <= nx < row and 0 <= ny < col and heights[nx][ny] >= heights[x][y]
and not arr[nx][ny]):
arr[nx][ny] = 1
que.append([nx, ny])
pacific = [[0] * col for _ in range(row)]
atlantic = [[0] * col for _ in range(row)]
for i in range(col):
bfs(0, i, pacific)
bfs(row - 1, i, atlantic)
for i in range(row):
bfs(i, 0, pacific)
bfs(i, col - 1, atlantic)
return [[i, j] for i in range(row) for j in range(col) if pacific[i][j] and atlantic[i][j]]
827. 最大人工岛¶
题解:
本题首先需要找到所有岛屿并记录不同岛屿的面积,然后遍历所有海洋,并计算每个海洋周围岛屿的面积和。几个需要注意的点:
-
可以直接更改元数组给不同岛屿做标记
-
需要注意一块海洋周围四个位置的岛屿可能重复,这里需要注意;
-
另外当所有区域都是岛屿时,没有海洋,因此需要先把最大的岛屿面积算出来
-
DFS
class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
n, idx, ans = len(grid), 2, 0
def dfs(x, y):
grid[x][y] = idx
area = 1
for dir in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
ni, nj = x + dir[0], y + dir[1]
if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] == 1:
area += dfs(ni, nj)
return area
size_map = {}
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
area = dfs(i, j)
size_map[idx] = area
idx += 1
ans = max(ans, area)
for i in range(n):
for j in range(n):
if grid[i][j] == 0:
visited_idx = {0}
cur = 1
for dir in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
ni, nj = i + dir[0], j + dir[1]
if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] not in visited_idx:
visited_idx.add(grid[ni][nj])
cur += size_map[grid[ni][nj]]
ans = max(cur, ans)
return ans
- BFS
class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
n, idx, ans = len(grid), 2, 0
def bfs(x, y):
grid[x][y] = idx
que = deque([[x, y]])
area = 1
while que:
i, j = que.popleft()
for dir in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
ni, nj = i + dir[0], j + dir[1]
if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] == 1:
area += 1
que.append([ni, nj])
grid[ni][nj] = idx
return area
size_map = {}
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
area = bfs(i, j)
size_map[idx] = area
idx += 1
ans = max(ans, area)
for i in range(n):
for j in range(n):
if grid[i][j] == 0:
visited_idx = {0}
cur = 1
for dir in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
ni, nj = i + dir[0], j + dir[1]
if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] not in visited_idx:
visited_idx.add(grid[ni][nj])
cur += size_map[grid[ni][nj]]
ans = max(cur, ans)
return ans
127. 单词接龙¶
题解:
因为本题需要找到最短路径,因此需要用BFS。==需要注意的是本题只能用队列,因为必须逐层递进才能找到最小路径,使用列表是可以找到所有路径==
- BFS
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
mapping = {beginWord: 1}
que = deque([beginWord])
while que:
word = que.popleft()
pos = mapping[word]
for i in range(len(word)):
word_list = list(word)
for j in range(26):
word_list[i] = chr(ord('a') + j)
new_word = ''.join(word_list)
if new_word in wordList and new_word not in mapping:
if new_word == endWord:
return pos + 1
que.append(new_word)
mapping[new_word] = pos + 1
return 0
841. 钥匙和房间¶
题解:
本题是理解深度优先搜索与栈及递归、广度优先搜索与队列的好题
- BFS
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
visited, queue = {0}, [0]
while queue:
room_index = queue.pop()
for key in rooms[room_index]:
if key not in visited:
visited.add(key)
queue.insert(0,key)
return len(visited) == len(rooms)
- DFS
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
visited, stack = {0}, [0]
while stack:
room_index = stack.pop()
for key in rooms[room_index]:
if key not in visited:
visited.add(key)
stack.append(key)
return len(visited) == len(rooms)
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
visited = {0}
def dfs(room_index,visited):
visited.add(room_index)
for key in rooms[room_index]:
if key not in visited: dfs(key,visited)
dfs(0,visited)
return len(visited) == len(rooms)
463. 岛屿的周长¶
题解:
本题当作几何题来做就行,每块岛屿边长减去邻边数量*2,其中邻边数量可以只考虑每块陆地的上左/上右/下右/下左,因为每个邻边总会重复计算一次
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
area, cover = 0, 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
area += 1
if i - 1 >= 0 and grid[i - 1][j] == 1:
cover += 1
if j - 1 >= 0 and grid[i][j - 1] == 1:
cover += 1
return area * 4 - cover * 2