Leetcode 课程表
这段代码的算法思想是基于**深度优先搜索（DFS）**来检测图中的环路，从而判断是否可以完成所有课程。具体来说，我们将每门课程和它的先修关系视为一个有向图，问题的核心就是判断这个有向图中是否存在环路。如果有环路，则说明有课程之间存在相互依赖的关系，导致无法完成所有课程；如果没有环路，则说明可以按顺序完成所有课程。
代码思路解析：
-
图的表示：
- 使用邻接表（
adjList）表示图，adjList[i]存储的是课程i的所有后续课程，即要先完成i才能完成的课程列表。 - 遍历
prerequisites数组，为每个先修关系[a, b]，在adjList[b]中添加a，表示完成课程b是课程a的前置条件。
- 使用邻接表（
-
节点访问状态（
visitState数组）：visitState[i]用于记录每门课程的访问状态：0表示未访问，1表示正在访问（即当前 DFS 路径上），2表示已完全访问（即 DFS 已处理完该节点及其所有后续节点）。
- 这种状态设置的目的是为了检测环路，如果在 DFS 中再次访问到一个状态为
1的节点，就说明存在环路。
-
DFS 检测环路：
- 对每一门课程执行 DFS。如果当前课程状态是
1，表示存在环路，返回false。 - 如果当前课程状态是
2，表示该课程已经处理完成，不存在环路，可以直接返回当前课程节点判断的true。 - 否则，将当前课程状态设为
1，然后递归处理所有后续课程。 - 在递归完成后，将当前课程状态设为
2，表示该课程已经完全访问完毕，未检测到环路。
- 对每一门课程执行 DFS。如果当前课程状态是
-
返回结果：
- 如果在任何一次 DFS 中检测到环路，立即返回
false。 - 如果所有课程都能被成功访问且无环路，返回整体结果的
true，表示可以完成所有课程。
- 如果在任何一次 DFS 中检测到环路，立即返回
复杂度分析：
- 时间复杂度：
O(V + E)，其中V是课程数量，E是先修关系数量。我们需要遍历所有课程和所有先修关系。 - 空间复杂度：
O(V + E)，用于存储图的邻接表以及访问状态数组。
总结：
这个算法的核心在于将问题转换为图中的环检测问题。通过使用 DFS 并结合访问状态来检测环路，我们可以有效判断课程计划是否可行。
java 代码
class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {//首先构建有向图的存储List<List<Integer>> adjList = new ArrayList<>();for(int i = 0; i < numCourses; ++i) {adjList.add(new ArrayList<>());}for(int[] prerequisite : prerequisites) {adjList.get(prerequisite[1]).add(prerequisite[0]);}//然后DFS过程, 首先创建访问状态数组//0代表尚未访问过,1代表访问转换后的状态,2代表当前节点及其所有相邻节点都不存在环int[] visitState = new int[numCourses];for(int i = 0; i < numCourses; ++i) { //每个图节点(课程)进行dfs过程if(!dfs(i, adjList, visitState)) { //dfs()返回false,当存在环时return false;}}return true;}private boolean dfs(int course, List<List<Integer>> adjList, int[] visitState) {if(visitState[course] == 1) {return false;}if(visitState[course] == 2) {return true; //这里返回的true代表的是当前课程节点不存在冲突,而不是所有课程都不存在冲突} //说明当前课程节点的访问状态是0,尚未被访问过//访问当前节点,将其访问状态改变visitState[course] = 1;for(int nextCourse : adjList.get(course)) { //遍历所有相邻节点if(!dfs(nextCourse, adjList, visitState)) {//如果存在环return false;}} //执行到这里说明当前节点的所有邻接节点都不存在环//更新节点访问状态, 2代表当前节点及其所有相邻节点都不存在环visitState[course] = 2;return true;}
}