图论
更新: 9/14/2025 字数: 0 字 时长: 0 分钟
岛屿数量
java
/**
* <p>此方法解决“岛屿数量”问题，采用<strong>深度优先搜索 (DFS)</strong> 的方式。</p>
* <p>核心思想：将每个 '1'（陆地）视为图中的一个节点，相邻的陆地之间有边。
* 问题转化为计算图中的连通分量数量。
* 当我们发现一个陆地单元格时，说明我们发现了一个新岛屿。
* 为了不重复计数这个岛屿的其它部分，我们利用 DFS 遍历这个岛屿的所有陆地单元格，
* 并将其标记为已访问（通过将其从 '1' 改为 '0'，模拟“淹没”岛屿）。
* 每当主遍历循环中找到一个未访问的 '1'，就增加岛屿计数器。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>主函数 {@code numIslands(grid)}：</strong>
* <ul>
* <li><strong>参数：</strong> {@code grid} 二维字符数组，代表网格。</li>
* <li><strong>返回：</strong> 岛屿的总数量。</li>
* <li><strong>基本情况：</strong>
* <ul>
* <li>{@code if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;}：
* 如果网格为空，返回 0。</li>
* </ul>
* </li>
* <li><strong>初始化：</strong>
* <ul>
* <li>{@code int rows = grid.length;}</li>
* <li>{@code int cols = grid[0].length;}</li>
* <li>{@code int numIslands = 0;}：初始化岛屿计数器。</li>
* </ul>
* </li>
* <li><strong>遍历网格：</strong>
* <ul>
* <li>使用嵌套循环 {@code for (int r = 0; r < rows; r++)} 和 {@code for (int c = 0; c < cols; c++)} 遍历每一个单元格。</li>
* <li><strong>发现陆地：</strong>
* <ul>
* <li>{@code if (grid[r][c] == '1')}：如果当前单元格是陆地 (并且之前没有被访问过，因为被访问过的 '1' 会变成 '0')。
* <ul>
* <li>{@code numIslands++;}：增加岛屿计数。</li>
* <li>{@code dfs(grid, r, c);}：从当前单元格启动 DFS，将这个岛屿的所有陆地单元格都标记为 '0'。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* <li>{@code return numIslands;}：返回最终的岛屿数量。</li>
* </ul>
* </li>
* <li><strong>辅助 DFS 函数 {@code dfs(grid, r, c)}：</strong>
* <ul>
* <li><strong>参数：</strong> {@code grid} 网格，{@code r} 当前行索引，{@code c} 当前列索引。</li>
* <li><strong>返回：</strong> {@code void}。此函数直接修改网格，将其陆地单元格标记为 '0'。</li>
* <li><strong>边界条件 (递归终止条件)：</strong>
* <ul>
* <li>{@code if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == '0')}：
* <ul>
* <li>如果当前坐标超出网格的有效范围。</li>
* <li>或者当前单元格是水（'0'），这包括原始是水和已经被 DFS 访问过的陆地。</li>
* <li>满足以上任何一个条件，则停止进一步搜索，直接返回。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>核心逻辑：</strong>
* <ul>
* <li>{@code grid[r][c] = '0';}：将当前陆地单元格标记为水，表示它已经被访问（“淹没”）了。</li>
* <li><strong>递归访问相邻单元格：</strong>
* <ul>
* <li>{@code dfs(grid, r + 1, c);} (向下)</li>
* <li>{@code dfs(grid, r - 1, c);} (向上)</li>
* <li>{@code dfs(grid, r, c + 1);} (向右)</li>
* <li>{@code dfs(grid, r, c - 1);} (向左)</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(R * C)}。
* <ul>
* <li>其中 {@code R} 是网格的行数，{@code C} 是网格的列数。</li>
* <li>主循环会遍历每个单元格一次 (R * C)。</li>
* <li>DFS 函数中，每个陆地单元格最多被访问和修改一次。因为一旦被访问，它就会被标记为 '0'，不会再次进入 DFS。</li>
* <li>因此，总时间复杂度是 {@code O(R * C)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(R * C)} (最坏情况)。
* <ul>
* <li>主要是递归调用栈的深度。在最坏情况，整个网格都是陆地，DFS 递归深度可以达到 {@code R * C}。</li>
* <li>在最好情况（例如，只有一行或一列），{@code H = min(R, C)}。</li>
* <li>在平均情况或其他情况，取决于连通分量的形状。</li>
* </ul>
* </li>
* </ul>
*/
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0; // 空网格，没有岛屿
}
int rows = grid.length;
int cols = grid[0].length;
int numIslands = 0; // 岛屿计数
// 遍历整个网格
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
// 如果发现一个陆地单元格 '1'
if (grid[r][c] == '1') {
numIslands++; // 岛屿数量加一
// 从这个陆地单元格开始，使用 DFS 淹没整个岛屿
// 这样这个岛屿的所有部分都被标记为 '0'，后续不会重复计数
dfs(grid, r, c);
}
}
}
return numIslands;
}
/**
* 深度优先搜索 (DFS) 辅助函数，用于“淹没”一个岛屿。
* 从 (r, c) 开始，将其及所有相邻的陆地单元格都标记为 '0'。
*
* @param grid 网格
* @param r 当前行索引
* @param c 当前列索引
*/
private void dfs(char[][] grid, int r, int c) {
// 边界条件：
// 1. 坐标超出网格范围
// 2. 当前单元格是水 ('0') -- 包括原始是水和已经被访问过的陆地
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == '0') {
return;
}
// 将当前陆地单元格标记为 '0'，表示已访问/已淹没
grid[r][c] = '0';
// 递归访问相邻的陆地单元格（上、下、左、右）
dfs(grid, r + 1, c); // 向下
dfs(grid, r - 1, c); // 向上
dfs(grid, r, c + 1); // 向右
dfs(grid, r, c - 1); // 向左
}腐烂的橘子
java
/**
* <p>此方法解决“腐烂的橘子”问题，采用<strong>广度优先搜索 (BFS)</strong> 的方式。</p>
* <p>核心思想：问题要求计算腐烂所有新鲜橘子所需的最少分钟数，且腐烂过程是同时向四周扩散的，
* 这正是 BFS 解决最短路径/层序遍历问题的典型场景。这是一个<strong>多源 BFS</strong> 问题，
* 所有初始的腐烂橘子同时开始扩散，就像洪水从多个源头同时蔓延。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>初始化：</strong>
* <ul>
* <li>{@code rows}, {@code cols}：获取网格的维度。</li>
* <li>{@code queue} (Type: {@code Queue<int[]>})：用于存储当前分钟腐烂橘子的坐标 {@code [r, c]}。</li>
* <li>{@code freshOranges}：计数器，记录网格中新鲜橘子的初始总数。</li>
* <li>遍历整个 {@code grid}：
* <ul>
* <li>如果遇到 {@code grid[r][c] == 2} (腐烂橘子)，将其坐标 {@code [r, c]} 加入 {@code queue}。</li>
* <li>如果遇到 {@code grid[r][c] == 1} (新鲜橘子)，{@code freshOranges++}。</li>
* </ul>
* </li>
* <li><strong>特殊情况处理：</strong> {@code if (freshOranges == 0) return 0;}：如果一开始就没有新鲜橘子，直接返回 0 分钟。</li>
* </ul>
* </li>
* <li><strong>BFS 循环：</strong>
* <ul>
* <li>{@code minutes = 0;}：初始化分钟计数器。</li>
* <li>{@code directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}}：定义四个方向的偏移量。</li>
* <li>{@code while (!queue.isEmpty() && freshOranges > 0)}：
* <ul>
* <li><strong>处理当前层（当前分钟腐烂橘子感染新橘子）：</strong>
* <ul>
* <li>{@code int size = queue.size();}：获取当前队列中腐烂橘子的数量。这些橘子将在本分钟内进行感染。</li>
* <li>{@code for (int i = 0; i < size; i++)}：遍历当前队列中的所有橘子：
* <ul>
* <li>{@code int[] rotten = queue.poll();}：取出队首的一个腐烂橘子。</li>
* <li>对这个橘子的四个相邻方向进行检查：
* <ul>
* <li>{@code int newR = rotten[0] + dr;}</li>
* <li>{@code int newC = rotten[1] + dc;}</li>
* <li><strong>检查有效性：</strong> {@code if (newR >= 0 && newR < rows && newC >= 0 && newC < cols && grid[newR][newC] == 1)}
* <ul>
* <li>如果新坐标合法，并且是新鲜橘子：</li>
* <li>{@code grid[newR][newC] = 2;}：将其标记为腐烂。</li>
* <li>{@code queue.offer(new int[]{newR, newC});}：将新腐烂的橘子加入队列，它将在下一分钟感染其他橘子。</li>
* <li>{@code freshOranges--;}：减少新鲜橘子计数。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>分钟数递增：</strong>
* <ul>
* <li>{@code if (freshOranges > 0)}：
* {@code minutes++;}：只有当这一分钟结束后，仍然有新鲜橘子需要腐烂，并且队列里确实有新的腐烂橘子（可以在下一分钟继续感染）时，才增加分钟数。
* 这样可以避免当最后一批橘子腐烂后，{@code minutes} 还会多加 1 的情况。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>结果判断：</strong>
* <ul>
* <li>{@code if (freshOranges == 0)}：如果所有新鲜橘子都成功腐烂，返回 {@code minutes}。</li>
* <li>{@code else}：如果循环结束后仍有新鲜橘子未腐烂（说明它们是不可达的），返回 {@code -1}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(R * C)}。
* <ul>
* <li>其中 {@code R} 是网格的行数，{@code C} 是网格的列数。</li>
* <li>每个单元格（橘子或空单元格）最多会被访问一次（在初始化阶段加入队列，或在 BFS 阶段被检查）。</li>
* <li>每个新鲜橘子最多会从 {@code 1} 变为 {@code 2} 一次。</li>
* <li>每个腐烂橘子最多会被从队列中取出一次，并检查其四个方向的邻居。</li>
* <li>因此，总时间复杂度是 {@code O(R * C)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(R * C)} (最坏情况)。
* <ul>
* <li>队列中最多存储所有的腐烂橘子坐标。在最坏情况下，所有陆地在同一分钟内腐烂，队列可能包含 {@code R * C} 个元素。</li>
* </ul>
* </li>
* </ul>
*/
public int orangesRotting(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0; // 空网格，无需腐烂
}
int rows = grid.length;
int cols = grid[0].length;
int freshOranges = 0; // 新鲜橘子计数
Queue<int[]> queue = new LinkedList<>(); // BFS 队列，存储腐烂橘子的坐标
// 第一次遍历网格，初始化队列和新鲜橘子数量
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 2) {
queue.offer(new int[]{r, c}); // 初始腐烂的橘子加入队列
} else if (grid[r][c] == 1) {
freshOranges++; // 统计新鲜橘子数量
}
}
}
// 如果没有新鲜橘子，则不需要时间，直接返回 0
if (freshOranges == 0) {
return 0;
}
int minutes = 0; // 记录经过的分钟数
// 定义四个方向的偏移量：右、左、下、上
int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
// BFS 核心循环：当队列不空且还有新鲜橘子时继续
// Queue.isEmpty() 负责判断是否所有可达橘子都已处理
// freshOranges > 0 负责判断是否还有橘子未腐烂（可能不可达）
while (!queue.isEmpty() && freshOranges > 0) {
int size = queue.size(); // 获取当前层有多少腐烂橘子，这些橘子将在这一分钟内感染新橘子
// 处理当前层的所有腐烂橘子
for (int i = 0; i < size; i++) {
int[] rotten = queue.poll(); // 取出当前腐烂橘子
int r = rotten[0];
int c = rotten[1];
// 检查其四个方向的相邻单元格
for (int[] dir : directions) {
int newR = r + dir[0];
int newC = c + dir[1];
// 检查新坐标是否在网格内，并且是一个新鲜橘子
if (newR >= 0 && newR < rows && newC >= 0 && newC < cols && grid[newR][newC] == 1) {
grid[newR][newC] = 2; // 将新鲜橘子标记为腐烂
queue.offer(new int[]{newR, newC}); // 新腐烂的橘子加入队列，将在下一分钟感染
freshOranges--; // 新鲜橘子数量减一
}
}
}
// 注意：只有当这一分钟确实有新的橘子被感染并加入队列时（即队列不为空），
// 且仍有新鲜橘子未腐烂时，才增加分钟数。
// 否则，如果队列已经空了（表示没有新的橘子可以腐烂了），minutes 不应再增加。
// 另一种写法是，在内层循环结束后，如果 freshOranges 在本次循环中减少了，
// 且 outer queue is not empty, minutes++ (更严谨，但本方法中由于 freshOranges>0 检查，
// 最终会收敛，不额外增加分钟数)
if (!queue.isEmpty()) { // 这一层感染结束后，如果队列还有元素，说明下一分钟还有橘子要腐烂
minutes++;
}
}
// 最终判断：如果所有新鲜橘子都腐烂了，返回分钟数
if (freshOranges == 0) {
return minutes;
} else {
// 否则，说明有新鲜橘子无法被腐烂
return -1;
}
}课程表
java
/**
* <p>此方法解决“课程表”问题，采用<strong>深度优先搜索 (DFS) 和状态标记</strong>来检测有向图中的环。</p>
* <p>核心思想：将课程和先修课程关系构造成一个有向图。如果图中存在环，则无法完成所有课程；如果无环，则可完成。
* DFS 可以用来检测环。在 DFS 遍历过程中，我们使用一个 {@code visited} 数组来标记节点的三种状态：</p>
*
* <ol>
* <li>{@code 0}：未被访问。</li>
* <li>{@code 1}：正在访问中（当前在递归栈中，表示正在探索从它出发的路径）。</li>
* <li>{@code 2}：已访问完成（所有从它出发的路径都已探索完毕，并且没有发现环）。</li>
* </ol>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>构建图：</strong>
* <ul>
* <li>{@code List<List<Integer>> graph = new ArrayList<>();}：使用邻接表表示图。{@code graph.get(i)} 存储所有依赖于课程 {@code i} 的课程。
* 即，{@code graph[bi]} 包含 {@code ai}，意味着 {@code bi -> ai} (要学 {@code ai} 必须先学 {@code bi})。</li>
* <li>根据 {@code prerequisites} 数组，填充 {@code graph}。</li>
* </ul>
* </li>
* <li><strong>状态数组 {@code visited}：</strong>
* <ul>
* <li>{@code int[] visited = new int[numCourses];}：大小为 {@code numCourses}。</li>
* <li>初始所有元素都为 {@code 0} (未访问)。</li>
* </ul>
* </li>
* <li><strong>主函数 {@code canFinish(numCourses, prerequisites)}：</strong>
* <ul>
* <li>遍历所有课程 {@code i} 从 {@code 0} 到 {@code numCourses - 1}：
* <ul>
* <li>{@code if (visited[i] == 0)}：如果当前课程 {@code i} 未被访问过，对其启动 DFS。</li>
* <li>{@code if (!dfs(i, graph, visited))}：如果 DFS 返回 {@code false} (表示发现了环)，则直接返回 {@code false}。</li>
* </ul>
* </li>
* <li>如果所有课程都 DFS 完毕且没有发现环，则返回 {@code true}。</li>
* </ul>
* </li>
* <li><strong>DFS 辅助函数 {@code dfs(course, graph, visited)}：</strong>
* <ul>
* <li><strong>参数：</strong> {@code course} 当前正在访问的课程，{@code graph} 邻接表，{@code visited} 状态数组。</li>
* <li><strong>返回：</strong> {@code boolean}。{@code true} 表示从 {@code course} 开始的路径无环，{@code false} 表示有环。</li>
* <li><strong>基本情况 (递归终止条件)：</strong>
* <ul>
* <li>{@code if (visited[course] == 1)}：<strong>发现环！</strong>
* <ul>
* <li>如果当前课程 {@code course} 正处于“正在访问中”状态（即它在当前的递归栈上），
* 而我们又再次遇到了它，说明存在一条回边，形成了环。返回 {@code false}。</li>
* </ul>
* </li>
* <li>{@code if (visited[course] == 2)}：<strong>已访问完成</strong>
* <ul>
* <li>如果当前课程 {@code course} 已经完全访问过（并且之前已经确认它无环），直接返回 {@code true}。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>核心逻辑：</strong>
* <ul>
* <li>{@code visited[course] = 1;}：将当前课程标记为“正在访问中”。</li>
* <li><strong>遍历其所有邻居 (prerequisites 的后续课程)：</strong>
* <ul>
* <li>{@code for (int nextCourse : graph.get(course))}：</li>
* <li>{@code if (!dfs(nextCourse, graph, visited))}：如果从任何一个 {@code nextCourse} 开始的 DFS 发现了环，则当前课程也位于环中。返回 {@code false}。</li>
* </ul>
* </li>
* <li>{@code visited[course] = 2;}：<strong>所有子孙节点都已访问完毕且无环</strong>，将当前课程标记为“已访问完成”。</li>
* <li>返回 {@code true} (表示从当前课程开始的路径无环)。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(V + E)}。
* <ul>
* <li>其中 {@code V} 是课程数量 {@code numCourses} (节点数)，{@code E} 是先修课程关系的数量 (边数)。</li>
* <li>构建图需要 {@code O(V + E)}。</li>
* <li>每个节点和每条边在 DFS 中最多被访问一次。</li>
* <li>因此，总时间复杂度是 {@code O(V + E)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(V + E)}。
* <ul>
* <li>邻接表 {@code graph} 占用 {@code O(V + E)} 空间。</li>
* <li>{@code visited} 数组占用 {@code O(V)} 空间。</li>
* <li>递归调用栈的深度在最坏情况下为 {@code O(V)} (例如，一条不间断的长链)。</li>
* <li>因此，总空间复杂度是 {@code O(V + E)}。</li>
* </ul>
* </li>
* </ul>
*/
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 1. 构建图 (邻接表表示)
// graph[i] 存储所有依赖于课程 i 的课程 (即从 i 指向 j 的边)，
// 换句话说，要学 graph[i] 中的课程，需要先学 i。
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
for (int[] prerequisite : prerequisites) {
int course = prerequisite[0]; // 要学习的课程
int preCourse = prerequisite[1]; // 先修课程
// 添加从 preCourse 到 course 的边
// 表示如果学习 course，则 preCourse 必须是其前置依赖
graph.get(preCourse).add(course);
}
// 2. 状态数组
// visited[i] = 0: 课程 i 未被访问
// visited[i] = 1: 课程 i 正在访问中 (在当前 DFS 递归栈中)
// visited[i] = 2: 课程 i 已访问完成 (从它出发的所有路径都已探索完毕且无环)
int[] visited = new int[numCourses];
// 3. 对每门课程进行 DFS 遍历，检测是否存在环
for (int i = 0; i < numCourses; i++) {
// 如果课程 i 尚未被访问过，则对其启动 DFS
if (visited[i] == 0) {
// 如果 DFS 返回 false，说明存在环，无法完成所有课程
if (!dfs(i, graph, visited)) {
return false;
}
}
}
// 如果所有课程都 DFS 完毕且没有发现环，则可以完成所有课程
return true;
}
/**
* 深度优先搜索 (DFS) 辅助函数，用于检测图中是否存在环。
*
* @param course 当前正在访问的课程
* @param graph 邻接表表示的图
* @param visited 课程访问状态数组
* @return 如果从当前课程开始的路径中存在环，返回 false；否则返回 true。
*/
private boolean dfs(int course, List<List<Integer>> graph, int[] visited) {
// 1. 如果当前课程正在访问中 (visited[course] == 1)，说明遇到了一个回边，存在环
if (visited[course] == 1) {
return false;
}
// 2. 如果当前课程已经访问完成 (visited[course] == 2)，说明从它出发的路径已经确认无环，直接返回 true
if (visited[course] == 2) {
return true;
}
// 3. 将当前课程标记为“正在访问中”
visited[course] = 1;
// 4. 遍历当前课程的所有邻居 (即依赖于当前课程的后续课程)
for (int nextCourse : graph.get(course)) {
// 如果从任何一个 nextCourse 开始的 DFS 发现了环，则当前路径也存在环
if (!dfs(nextCourse, graph, visited)) {
return false; // 发现环，立即返回 false
}
}
// 5. 当前课程的所有邻居都已访问完毕且无环，将当前课程标记为“已访问完成”
visited[course] = 2;
// 6. 从当前课程开始的路径无环
return true;
}java
/**
* <p>此方法解决“课程表”问题，采用<strong>广度优先搜索 (BFS) 的 Kahn 算法</strong>，基于入度表。</p>
* <p>核心思想：如果一个有向无环图 (DAG) 存在拓扑排序，那么一定可以通过不断移除入度为 0 的节点来完成排序。
* 如果最终无法移除所有节点，则说明图中存在环。
* 因此，我们可以维护每个课程的<strong>入度</strong>（有多少门课程是它的先修课程），并使用 BFS 来进行拓扑排序模拟。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>构建图和入度表：</strong>
* <ul>
* <li>{@code List<List<Integer>> graph = new ArrayList<>();}：使用邻接表表示图。{@code graph.get(i)} 存储所有依赖于课程 {@code i} 的课程。
* 即，对于 {@code [ai, bi]}，我们添加从 {@code bi} 到 {@code ai} 的边，表示 {@code bi} 是 {@code ai} 的先修课程。</li>
* <li>{@code int[] inDegree = new int[numCourses];}：大小为 {@code numCourses}，{@code inDegree[i]} 存储课程 {@code i} 的入度。</li>
* <li>根据 {@code prerequisites} 数组，填充 {@code graph} 和 {@code inDegree}：
* <ul>
* <li>{@code graph.get(preCourse).add(course);} （{@code preCourse} 是 {@code course} 的先修课程）</li>
* <li>{@code inDegree[course]++;} （{@code course} 的入度增加 1）</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>初始化队列：</strong>
* <ul>
* <li>{@code Queue<Integer> queue = new LinkedList<>();}：创建一个队列，用于存储入度为 0 的课程。</li>
* <li>遍历所有课程 {@code i} 从 {@code 0} 到 {@code numCourses - 1}：
* <ul>
* <li>{@code if (inDegree[i] == 0)}：如果课程 {@code i} 的入度为 0，说明它没有先修课程，可以最先学习。将其加入队列。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>BFS 拓扑排序：</strong>
* <ul>
* <li>{@code int count = 0;}：记录已经完成（即入队并出队）的课程数量。</li>
* <li>{@code while (!queue.isEmpty())}：当队列不为空时循环：
* <ul>
* <li>{@code int course = queue.poll();}：从队列中取出一门可以学习的课程。</li>
* <li>{@code count++;}：已完成课程数量加 1。</li>
* <li><strong>更新邻居的入度：</strong>
* <ul>
* <li>{@code for (int nextCourse : graph.get(course))}：遍历所有依赖于当前完成课程 {@code course} 的后续课程 {@code nextCourse}。</li>
* <li>{@code inDegree[nextCourse]--;}：将 {@code nextCourse} 的入度减 1，因为其先修课程 {@code course} 已经完成。</li>
* <li>{@code if (inDegree[nextCourse] == 0)}：如果 {@code nextCourse} 的入度变为 0，说明它现在所有先修课程都已完成，可以学习了。将其加入队列。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>结果判断：</strong>
* <ul>
* <li>{@code if (count == numCourses)}：如果 {@code count} 等于总课程数 {@code numCourses}，说明所有课程都成功进行了拓扑排序，即图中无环。返回 {@code true}。</li>
* <li>{@code else}：如果 {@code count} 小于 {@code numCourses}，说明有部分课程无法入队完成（因为它们的入度永远不会变为 0），这说明图中存在环。返回 {@code false}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(V + E)}。
* <ul>
* <li>其中 {@code V} 是课程数量 {@code numCourses} (节点数)，{@code E} 是先修课程关系的数量 (边数)。</li>
* <li>构建图和入度表需要 {@code O(V + E)}。</li>
* <li>BFS 过程中，每个节点最多入队和出队一次，每条边最多被访问一次（当其起点的课程出队时）。</li>
* <li>因此，总时间复杂度是 {@code O(V + E)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(V + E)}。
* <ul>
* <li>邻接表 {@code graph} 占用 {@code O(V + E)} 空间。</li>
* <li>{@code inDegree} 数组占用 {@code O(V)} 空间。</li>
* <li>队列在最坏情况下（例如，所有课程都在同一“层”），可能包含 {@code O(V)} 个元素。</li>
* <li>因此，总空间复杂度是 {@code O(V + E)}。</li>
* </ul>
* </li>
* </ul>
*/
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 1. 构建图和入度表
List<List<Integer>> graph = new ArrayList<>();
int[] inDegree = new int[numCourses]; // 存储每个课程的入度
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
for (int[] prerequisite : prerequisites) {
int course = prerequisite[0]; // 依赖课程
int preCourse = prerequisite[1]; // 先修课程
// 添加从 preCourse 到 course 的边
// 表示要学 course，必须先学 preCourse
graph.get(preCourse).add(course);
inDegree[course]++; // course 的入度加 1
}
// 2. 初始化队列：将所有入度为 0 的课程加入队列
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
// 3. BFS 拓扑排序过程
int count = 0; // 记录已完成（即入队并出队）的课程数量
while (!queue.isEmpty()) {
int course = queue.poll(); // 取出队首课程，表示可以学习这门课程了
count++; // 完成的课程数量加 1
// 遍历当前课程的所有邻居 (即依赖于当前课程的后续课程)
for (int nextCourse : graph.get(course)) {
inDegree[nextCourse]--; // 将 nextCourse 的入度减 1，因为它的一门先修课程 course 已经完成
// 如果 nextCourse 的入度变为 0，说明它现在所有先修课程都已完成，可以学习
if (inDegree[nextCourse] == 0) {
queue.offer(nextCourse); // 将 nextCourse 加入队列
}
}
}
// 4. 判断结果：如果完成的课程数量等于总课程数量，则无环，可以完成所有课程
return count == numCourses;
}实现 Trie (前缀树)
java
/**
* <p>此类实现了 Trie (前缀树) 数据结构，包含初始化、插入单词、搜索单词和搜索前缀的功能。</p>
* <p>Trie 是一种树形数据结构，它利用字符串的公共前缀来减少存储空间，并能高效地检索字符串。</p>
*
* <h3>核心思想：</h3>
* <p>Trie 由一系列节点组成，每个节点代表一个字符。从根节点到任意一个节点的路径构成一个字符串前缀。
* 为了区分一个节点是否是完整单词的结尾，我们会在节点中设置一个布尔标记 {@code isEndOfWord}。</p>
*
* <p>每个 {@code TrieNode} 包含：
* <ul>
* <li>{@code children}: 一个数组 (或哈希表) 用于存储子节点。由于本题假设只包含小写英文字母，可以使用大小为 26 的数组，索引 {@code 0} 对应 {@code 'a'}，{@code 1} 对应 {@code 'b'} 等。</li>
* <li>{@code isEndOfWord}: 一个布尔值，如果从根节点到当前节点的路径构成一个已插入的完整单词，则为 {@code true}。</li>
* </ul>
* </p>
*/
public class Trie {
// Trie 的根节点
private TrieNode root;
/**
* TrieNode 类定义：
* 每个节点包含一个子节点数组和一个布尔标记。
*/
private static class TrieNode {
TrieNode[] children; // 存储 26 个小写英文字母的子节点
boolean isEndOfWord; // 标记从根到当前节点是否构成一个完整的单词
public TrieNode() {
children = new TrieNode[26]; // 默认全部为 null
isEndOfWord = false;
}
}
/**
* 初始化前缀树对象。
*/
public Trie() {
root = new TrieNode();
}
/**
* 向前缀树中插入字符串 word。
* 遍历单词的每个字符，如果路径不存在则创建新节点。
* 最后将最后一个字符对应的节点的 isEndOfWord 标记为 true。
*
* <h3>时间复杂度：</h3> O(L)，其中 L 是待插入单词的长度。
* 因为我们需要遍历单词的每个字符，每个字符的操作是常数时间。
*
* @param word 要插入的字符串
*/
public void insert(String word) {
TrieNode current = root;
for (char c : word.toCharArray()) {
int index = c - 'a'; // 计算字符对应的索引 (0-25)
if (current.children[index] == null) {
// 如果当前字符对应的子节点不存在，则创建新节点
current.children[index] = new TrieNode();
}
// 移动到下一个节点
current = current.children[index];
}
// 标记最后一个节点为单词的结尾
current.isEndOfWord = true;
}
/**
* 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false。
* 遍历单词的每个字符，如果路径中断（某个子节点为 null），则表示单词不存在。
* 最终到达的节点的 isEndOfWord 必须为 true。
*
* <h3>时间复杂度：</h3> O(L)，其中 L 是待搜索单词的长度。
*
* @param word 要搜索的字符串
* @return 如果单词存在于 Trie 中，返回 true；否则返回 false。
*/
public boolean search(String word) {
TrieNode current = root;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (current.children[index] == null) {
// 路径中断，单词不存在
return false;
}
current = current.children[index];
}
// 检查是否到达一个完整单词的结尾
return current.isEndOfWord;
}
/**
* 如果之前已经插入的字符串 word 的前缀之一为 prefix，返回 true；否则，返回 false。
* 遍历前缀的每个字符，只要路径存在即可。不需要检查 isEndOfWord。
*
* <h3>时间复杂度：</h3> O(L)，其中 L 是待搜索前缀的长度。
*
* @param prefix 要搜索的前缀
* @return 如果有任何一个单词以 prefix 开头，返回 true；否则返回 false。
*/
public boolean startsWith(String prefix) {
TrieNode current = root;
for (char c : prefix.toCharArray()) {
int index = c - 'a';
if (current.children[index] == null) {
// 路径中断，前缀不存在
return false;
}
current = current.children[index];
}
// 如果能成功遍历完所有前缀字符，说明该前缀存在
return true;
}
}贡献者
LI SIR