LeetCode 207. 课程表
题目描述
✅ 207. 课程表
思路分析
解法一：拓扑排序（BFS，推荐）
核心思路：
- 课程依赖关系构成有向图，能否完成所有课程等价于有向图中是否存在环。
- 将
prerequisites建图：[a, b]表示学a前必须先学b，即有向边b → a。- 统计每个节点的入度，将所有入度为 0 的节点加入队列（可以直接学的课程）。
- 每次弹出队首节点，将其所有邻居入度减 1；若某邻居入度变为 0，则入队。
- 统计处理的节点总数，若等于
numCourses则无环返回true，否则返回false。
复杂度分析：
- 时间复杂度：O(V + E)，其中 V 为课程数，E 为先修关系数
- 空间复杂度：O(V + E)，其中 V 为课程数，E 为先修关系数
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 建立邻接表和入度数组
List<List<Integer>> graph = new ArrayList<>();
int[] inDegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
// 构建有向图：pre[1] -> pre[0]
for (int[] pre : prerequisites) {
graph.get(pre[1]).add(pre[0]);
inDegree[pre[0]]++;
}
// 将所有入度为 0 的课程加入队列
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
int count = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
count++;
// 将邻居入度减 1，入度为 0 则入队
for (int next : graph.get(node)) {
if (--inDegree[next] == 0) {
queue.offer(next);
}
}
}
// 若处理的节点数等于课程总数，说明无环
return count == numCourses;
}
}
func canFinish(numCourses int, prerequisites [][]int) bool {
// 建立邻接表和入度数组
graph := make([][]int, numCourses)
inDegree := make([]int, numCourses)
for i := range graph {
graph[i] = []int{}
}
// 构建有向图：prev -> course
for _, pre := range prerequisites {
course, prev := pre[0], pre[1]
graph[prev] = append(graph[prev], course)
inDegree[course]++
}
// 将所有入度为 0 的课程加入队列
queue := []int{}
for i := 0; i < numCourses; i++ {
if inDegree[i] == 0 {
queue = append(queue, i)
}
}
count := 0
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
count++
// 将邻居入度减 1，入度为 0 则入队
for _, next := range graph[node] {
inDegree[next]--
if inDegree[next] == 0 {
queue = append(queue, next)
}
}
}
// 若处理的节点数等于课程总数，说明无环
return count == numCourses
}
解法二：DFS 检测环
核心思路：
- 对每个未访问节点进行 DFS，使用三色标记法检测有向图中的环。
0：未访问；1：访问中（在当前 DFS 路径上）；2：已完成访问。- 若 DFS 中遇到状态为
1的节点，说明当前路径上存在环，返回false。- 所有节点均完成访问且未发现环，则返回
true。
复杂度分析：
- 时间复杂度：O(V + E)，其中 V 为课程数，E 为先修关系数
- 空间复杂度：O(V + E)，其中 V 为递归栈深度，E 为邻接表大小
class Solution {
// 0: 未访问，1: 访问中，2: 已完成
private int[] visited;
private List<List<Integer>> graph;
public boolean canFinish(int numCourses, int[][] prerequisites) {
graph = new ArrayList<>();
visited = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
// 构建有向图
for (int[] pre : prerequisites) {
graph.get(pre[1]).add(pre[0]);
}
// 对每个未访问的节点进行 DFS
for (int i = 0; i < numCourses; i++) {
if (visited[i] == 0 && hasCycle(i)) {
return false;
}
}
return true;
}
private boolean hasCycle(int node) {
// 标记为访问中
visited[node] = 1;
for (int next : graph.get(node)) {
// 遇到访问中的节点，说明有环
if (visited[next] == 1) {
return true;
}
// 对未访问的节点继续 DFS
if (visited[next] == 0 && hasCycle(next)) {
return true;
}
}
// 标记为已完成
visited[node] = 2;
return false;
}
}
func canFinish(numCourses int, prerequisites [][]int) bool {
// 建立邻接表
graph := make([][]int, numCourses)
for i := range graph {
graph[i] = []int{}
}
for _, pre := range prerequisites {
graph[pre[1]] = append(graph[pre[1]], pre[0])
}
// 0: 未访问，1: 访问中，2: 已完成
visited := make([]int, numCourses)
var hasCycle func(node int) bool
hasCycle = func(node int) bool {
// 标记为访问中
visited[node] = 1
for _, next := range graph[node] {
// 遇到访问中的节点，说明有环
if visited[next] == 1 {
return true
}
// 对未访问的节点继续 DFS
if visited[next] == 0 && hasCycle(next) {
return true
}
}
// 标记为已完成
visited[node] = 2
return false
}
// 对每个未访问的节点进行 DFS
for i := 0; i < numCourses; i++ {
if visited[i] == 0 && hasCycle(i) {
return false
}
}
return true
}
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 210. 课程表 II | 中等 | 拓扑排序 |
| 269. 火星词典 | 困难 | 拓扑排序 |
| 444. 序列重建 | 中等 | 拓扑排序 |
| 630. 课程表 III | 困难 | 贪心、堆 |
| 802. 找到最终的安全状态 | 中等 | 拓扑排序、DFS |
| 851. 喧闹和富有 | 中等 | 拓扑排序 |
| 1136. 并行课程 | 中等 | 拓扑排序 |
| 1203. 项目管理 | 困难 | 拓扑排序 |
| 2115. 从给定原材料中找到所有可以做出的菜 | 中等 | 拓扑排序 |
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！