算法题：课程表
n 门课程，每一门课程都有一些先修课程。你的任务是判断你能不能按要求安排完这些课程。如果可以安排完，就返回 true，否则返回 false。深度优先搜索（DFS）
0：课程尚未访问1：课程正在访问中（即该课程是当前DFS栈的一部分）2：课程已经访问完毕
1），那就说明图中存在环，返回 false。否则，如果整个图遍历完成都没有问题，就返回 true。import java.util.*;
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 构建图
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
for (int[] pre : prerequisites) {
graph.get(pre[0]).add(pre[1]);
}
// 用来标记课程的状态
int[] visited = new int[numCourses];
// 对每门课程执行DFS
for (int i = 0; i < numCourses; i++) {
if (visited[i] == 0 && !dfs(graph, visited, i)) {
return false;
}
}
return true;
}
private boolean dfs(List<List<Integer>> graph, int[] visited, int course) {
// 如果该课程正在被访问，说明图中有环
if (visited[course] == 1) {
return false;
}
// 如果该课程已经被访问过，说明没有环
if (visited[course] == 2) {
return true;
}
// 标记为正在访问
visited[course] = 1;
// 访问所有依赖于当前课程的课程
for (int neighbor : graph.get(course)) {
if (!dfs(graph, visited, neighbor)) {
return false;
}
}
// 访问完当前课程的所有依赖，标记为已访问
visited[course] = 2;
return true;
}
}
visited数组来判断是否有环。拓扑排序（Kahn算法）
计算每个节点的入度。 使用一个队列存储所有入度为0的节点。 从队列中取出一个节点，处理它并减少与它相关的其他节点的入度。 如果最终所有节点都能被处理，说明图中没有环；如果有节点始终无法被处理，那就是有环。
import java.util.*;
public 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<>());
}
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 processedCourses = 0;
while (!queue.isEmpty()) {
int course = queue.poll();
processedCourses++;
// 更新依赖课程的入度
for (int neighbor : graph.get(course)) {
if (--inDegree[neighbor] == 0) {
queue.offer(neighbor);
}
}
}
// 如果所有课程都被处理了，就返回true
return processedCourses == numCourses;
}
}
对编程、职场感兴趣的同学，可以链接我，微信：coder301 拉你进入“程序员交流群”。
