图论是数学的一个分支，主要研究图的结构、性质以及图的应用。图论中的图是由顶点（也称为节点）和边组成的抽象结构，可以用来表示现实世界中的各种关系和结构，如社交网络、交通网络、电路网络等。以下是图论的一些基本概念：1. **顶点（Vertex）**：图中的基本

图论 (1) 岛屿数量 """ 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 """ res = 0 def dfs(grid, i, j): if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] == "0": return grid[i][j] = "0" dfs(grid, i-1, j) dfs(grid, i+1, j) dfs(grid, i, j-1) dfs(grid, i, j+1) for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == "1": dfs(grid, i, j) res += 1 return res (2) 腐烂的橘子 """ 在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一： - 值 0 代表空单元格； - 值 1 代表新鲜橘子； - 值 2 代表腐烂的橘子。 每分钟，腐烂的橘子周围 4 个方向上相邻 的新鲜橘子都会腐烂。返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。 """ row = len(grid) col = len(grid[0]) rotten = {(i, j) for i in range(row) for j in range(col) if grid[i][j] == 2} fresh = {(i, j) for i in range(row) for j in range(col) if grid[i][j] == 1} time = 0 while fresh: if not rotten: return -1 rotten = {(i + di, j + dj) for i, j in rotten for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)] if (i + di, j + dj) in fresh} fresh -= rotten time += 1 return time (3) 课程表 """ 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi]，表示如果要学习课程 ai 则 必须 先学习课程 bi。例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。 """ indegrees = [0 for _ in range(numCourses)] adjacency = [[] for _ in range(numCourses)] queue = collections.deque() for cur, pre in prerequisites: indegrees[cur] += 1 adjacency[pre].append(cur) for i in range(len(indegrees)): if not indegrees[i]: queue.append(i) while queue: pre = queue.popleft() numCourses -= 1 for cur in adjacency[pre]: indegrees[cur] -= 1 if not indegrees[cur]: queue.append(cur) return not numCourses (4) 前缀树 """ 请你实现 Trie 类： - Trie() 初始化前缀树对象。 - void insert(String word) 向前缀树中插入字符串 word。