跳转至

图论

简介

需要注意的点

  • 在深度优先搜索的时候数组的处理需要尤其注意,因为python中数组是可以在函数传递过程中被改变的,所以如果要复制数组的内容往往需要使用深拷贝arr[:];

题目

797. 所有可能的路径

image-20240229104758705

image-20240229104815945

题解:

  • 本题是深度优先搜索或广度优先搜索在图中的典型题目

  • 首先考虑深度优先搜索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. 岛屿数量

image-20240229145131114

image-20240229145142097

题解:

  • 每当发现一个岛屿时,将与其相连的其他陆地找出并把岛屿数量加一即可,因此可以采用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. 飞地的数量

image-20240229165614055

image-20240229165630245

题解:

本题关键点在于理解题意,题目需要找出不包含边界点的岛屿的面积,因此可以先对四条边进行搜索,将包含边界点的岛屿全部变为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. 太平洋大西洋水流问题

image-20240229203533524

image-20240229203550940

image-20240229203600609

题解:

本题仍然需要从边界出发,遍历边界附近更高的点。只是这道题的边界有两种情况,因此需要定义两个状态矩阵分别对应太平洋和大西洋边界的情况

  • 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. 最大人工岛

image-20240229221702581

题解:

本题首先需要找到所有岛屿并记录不同岛屿的面积,然后遍历所有海洋,并计算每个海洋周围岛屿的面积和。几个需要注意的点:

  1. 可以直接更改元数组给不同岛屿做标记

  2. 需要注意一块海洋周围四个位置的岛屿可能重复,这里需要注意;

  3. 另外当所有区域都是岛屿时,没有海洋,因此需要先把最大的岛屿面积算出来

  4. 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. 单词接龙

image-20240301094924923

题解:

因为本题需要找到最短路径,因此需要用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. 钥匙和房间

image-20240301134958690

题解:

本题是理解深度优先搜索与栈及递归、广度优先搜索与队列的好题

  • 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. 岛屿的周长

image-20240301141234383

image-20240301141246628

题解:

本题当作几何题来做就行,每块岛屿边长减去邻边数量*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