☆打卡算法☆LeetCode 207. 课程表 算法解析
大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个学期应该学习的课程数，判断是否可能完成所有课程的学习。”
题目链接：
来源：力扣（LeetCode）
2、题目描述
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。二、解题
1、思路分析
这道题需要先理解题意，题意要求判断是否可能完成所有课程的学习。
比如这个学期必须选修numCourses门课程，在选修某些课程之前需要先完成一些先修课程，先修课程存放在数组prerequisites中，是一个二维数组，表明某些课程前需要学习的先修课程。
也就是这些课程之前有一个先后顺序，也就是依赖关系，也就是做事情的先后顺序，比如说：
这个图叫做有向无环图，把一个有向无环图转成线性的排序就叫做拓扑排序。
对于给定的条件可以转成有向图G，给它的及诶单排列，如果满足：
- 图G中的任意一条有向边(u,v)，u在排列中都出现在v的前面，就称图G为有向无环图。
那么对于一个有向图，可以分为两种情况：
- 不是有向无环图，也就是不满足任意一条有向边(u,v)，u在排列中都出现在v的前面，那么就不存在满足要求的排列。
- 是有向无环图，但是它的拓扑排序可能不止一种。
求有向图G是否存在拓扑排序，可以判断是否有一种符合要求的课程学习顺序，可以使用深度优先搜索的流程，用一个栈来存储所有已经搜索完成的节点。
比如说搜索到节点u，如果它的所有相邻接点都已经搜索完成，也就是都在栈中，那么就可以将u入栈。
因为栈先入先出，那么u就在栈顶的位置，u就出现在所有u的相邻节点前，因此对于u是满足拓扑排序的要求的。
那么对整个图进行一次深度优先搜索，对每个节点回溯的时候，将该节点放入栈中，最后从栈顶到栈底的序列就是一种拓扑排序。
2、代码实现
代码参考：
class Solution {
List<List<Integer>> edges;
int[] visited;
boolean valid = true;
public boolean canFinish(int numCourses, int[][] prerequisites) {
edges = new ArrayList<List<Integer>>();
for (int i = 0; i < numCourses; ++i) {
edges.add(new ArrayList<Integer>());
}
visited = new int[numCourses];
for (int[] info : prerequisites) {
edges.get(info[1]).add(info[0]);
}
for (int i = 0; i < numCourses && valid; ++i) {
if (visited[i] == 0) {
dfs(i);
}
}
return valid;
}
public void dfs(int u) {
visited[u] = 1;
for (int v: edges.get(u)) {
if (visited[v] == 0) {
dfs(v);
if (!valid) {
return;
}
} else if (visited[v] == 1) {
valid = false;
return;
}
}
visited[u] = 2;
}
}
3、时间复杂度
时间复杂度：O(n+m)
其中n为课程数，m为先修课程的要求数，时间复杂度主要是对图进行深度优先搜索的时间复杂度。
空间复杂度：O(n+m)
其中n为课程数，m为先修课程的要求数，在深度优先搜索的过程中，需要最多O(n)的栈空间进行深度优先搜索，因此总时间复杂度为O(n+m)。
三、总结
由于只需要判断是否存在一种拓扑排序。
而栈仅仅是为了存放最终的拓扑排序结果。
那么可以只记录每个节点的状态，省去对应的栈空间开销。
腾讯云开发者
