BFS 经典双题：腐烂的橘子 + 课程表 | 拓扑排序入门必刷

目录

一、腐烂的橘子（中等）

题目描述

解题思路（多源 BFS）

完整代码

二、课程表（中等）

题目描述

解题思路（拓扑排序）

完整代码

核心考点总结

一、腐烂的橘子（中等）

题目描述

在给定的网格中，每个单元格可以有以下三个值之一：

• 0表示空单元格
• 1表示新鲜橘子
• 2表示腐烂的橘子

每分钟，任何与腐烂橘子相邻（上、下、左、右）的新鲜橘子都会腐烂。返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回-1。

解题思路（多源 BFS）

这是典型的多源 BFS问题：

1. 初始化队列：先遍历网格，把所有腐烂的橘子（值为2）加入队列，同时统计新鲜橘子的数量。
2. 分层 BFS：每一分钟处理队列中的所有腐烂橘子，把它们相邻的新鲜橘子腐烂，并加入队列。
3. 判断结果：如果新鲜橘子全部腐烂，返回分钟数；否则返回-1。

完整代码

java

运行

public class Solution { public int orangesRotting(int[][] grid) { int rows = grid.length; int cols = grid[0].length; Queue<int[]> 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）拓扑排序问题：

1. 构建邻接表和入度数组：用邻接表表示课程依赖关系，用入度数组统计每门课程的先修数。
2. 初始化队列：把入度为 0 的课程（没有先修条件）加入队列。
3. BFS 处理：每处理一门课程，把它的后继课程的入度减 1，如果入度变为 0，就加入队列。
4. 判断结果：如果处理的课程数等于总课程数，说明可以完成；否则存在环，无法完成。

完整代码

java

运行

public class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { // 1. 构建邻接表和入度数组 List<List<Integer>> 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 的课程入队 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 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 和拓扑排序的核心思想。