目录一、腐烂的橘子中等题目描述解题思路多源 BFS完整代码二、课程表中等题目描述解题思路拓扑排序完整代码核心考点总结一、腐烂的橘子中等题目描述在给定的网格中每个单元格可以有以下三个值之一0表示空单元格1表示新鲜橘子2表示腐烂的橘子每分钟任何与腐烂橘子相邻上、下、左、右的新鲜橘子都会腐烂。返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能返回-1。解题思路多源 BFS这是典型的多源 BFS问题初始化队列先遍历网格把所有腐烂的橘子值为2加入队列同时统计新鲜橘子的数量。分层 BFS每一分钟处理队列中的所有腐烂橘子把它们相邻的新鲜橘子腐烂并加入队列。判断结果如果新鲜橘子全部腐烂返回分钟数否则返回-1。完整代码java运行public class Solution { public int orangesRotting(int[][] grid) { int rows grid.length; int cols grid[0].length; Queueint[] queue new LinkedList(); int freshCount 0; int minutes 0; // 1. 初始化队列和新鲜橘子计数 for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 2) { queue.offer(new int[]{i, j}); } else if (grid[i][j] 1) { freshCount; } } } // 如果没有新鲜橘子直接返回 0 if (freshCount 0) return 0; // 方向数组上、下、左、右 int[][] dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 2. BFS 分层处理 while (!queue.isEmpty()) { int size queue.size(); for (int i 0; i size; i) { int[] curr queue.poll(); int x curr[0], y curr[1]; for (int[] dir : dirs) { int nx x dir[0]; int ny y dir[1]; if (nx 0 nx rows ny 0 ny cols grid[nx][ny] 1) { grid[nx][ny] 2; // 腐烂 freshCount--; queue.offer(new int[]{nx, ny}); } } } minutes; } // 3. 判断是否还有新鲜橘子 return freshCount 0 ? minutes - 1 : -1; } }二、课程表中等题目描述你这个学期必须选修numCourses门课程编号从0到numCourses-1。某些课程有先修条件例如选修课程0之前你需要先修课程1用[0,1]表示。判断是否可能完成所有课程的学习。解题思路拓扑排序这是典型的有向无环图DAG拓扑排序问题构建邻接表和入度数组用邻接表表示课程依赖关系用入度数组统计每门课程的先修数。初始化队列把入度为 0 的课程没有先修条件加入队列。BFS 处理每处理一门课程把它的后继课程的入度减 1如果入度变为 0就加入队列。判断结果如果处理的课程数等于总课程数说明可以完成否则存在环无法完成。完整代码java运行public class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { // 1. 构建邻接表和入度数组 ListListInteger adj new ArrayList(); int[] inDegree new int[numCourses]; for (int i 0; i numCourses; i) { adj.add(new ArrayList()); } for (int[] pre : prerequisites) { int course pre[0]; int prereq pre[1]; adj.get(prereq).add(course); inDegree[course]; } // 2. 初始化队列入度为 0 的课程入队 QueueInteger 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 curr queue.poll(); count; for (int next : adj.get(curr)) { inDegree[next]--; if (inDegree[next] 0) { queue.offer(next); } } } // 4. 判断是否可以完成所有课程 return count numCourses; } }核心考点总结表格题目核心算法关键技巧腐烂的橘子多源 BFS初始化所有腐烂橘子为起点分层处理课程表拓扑排序BFS入度数组 邻接表处理 DAG 依赖这两道题是 BFS 在不同场景下的经典应用掌握它们可以帮你快速理解多源 BFS 和拓扑排序的核心思想。