Leetcode 课程表

这段代码的算法思想是基于**深度优先搜索（DFS）**来检测图中的环路，从而判断是否可以完成所有课程。具体来说，我们将每门课程和它的先修关系视为一个有向图，问题的核心就是判断这个有向图中是否存在环路。如果有环路，则说明有课程之间存在相互依赖的关系，导致无法完成所有课程；如果没有环路，则说明可以按顺序完成所有课程。

代码思路解析：

1. 图的表示：

   • 使用邻接表（adjList）表示图，adjList[i]存储的是课程 i 的所有后续课程，即要先完成 i 才能完成的课程列表。
   • 遍历 prerequisites 数组，为每个先修关系 [a, b]，在 adjList[b] 中添加 a，表示完成课程 b 是课程 a 的前置条件。

2. 节点访问状态（visitState 数组）：

   • visitState[i] 用于记录每门课程的访问状态：
     • 0 表示未访问，
     • 1 表示正在访问（即当前 DFS 路径上），
     • 2 表示已完全访问（即 DFS 已处理完该节点及其所有后续节点）。
   • 这种状态设置的目的是为了检测环路，如果在 DFS 中再次访问到一个状态为 1 的节点，就说明存在环路。

3. DFS 检测环路：

   • 对每一门课程执行 DFS。如果当前课程状态是 1，表示存在环路，返回 false。
   • 如果当前课程状态是 2，表示该课程已经处理完成，不存在环路，可以直接返回当前课程节点判断的 true。
   • 否则，将当前课程状态设为 1，然后递归处理所有后续课程。
   • 在递归完成后，将当前课程状态设为 2，表示该课程已经完全访问完毕，未检测到环路。

4. 返回结果：

   • 如果在任何一次 DFS 中检测到环路，立即返回 false。
   • 如果所有课程都能被成功访问且无环路，返回整体结果的 true，表示可以完成所有课程。

复杂度分析：

• 时间复杂度：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;}
}