你这个学期必须选修 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.在有向图中任意选一个没有前驱的节点，（且输出）；
2.从图中删除该顶点 以及 所有以它为尾的边；
3.重复12， 直至全部节点均已输出，或图中不存在无前驱的顶点为止。
判断图节点是否有先驱节点，利用图节点的入度来计算，如果一个节点入度==0，则该节点没有前驱节点。
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 1.根据边的关系来构造图
List<Integer>[] graph = new List[numCourses]; //构造邻接表来存储图
for (int i=0; i<numCourses; i++) {
graph[i] = new ArrayList<>();
}
for(int[] pre : prerequisites) {
graph[pre[1]].add(pre[0]);
}
// 2.创建入度表
int[] inDegree = new int[numCourses];
for (int i=0; i<numCourses; i++) {
List<Integer> per = graph[i];
for (int j : per) {
inDegree[j] += 1;
}
}
// 3.入度为0的节点入队列，然后删除这个节点 以及所有关系（ 对应的节点的入度-1）
Queue<Integer> queue = new LinkedList<>();
for (int i=0; i<numCourses; i++) {
if(inDegree[i] == 0){
queue.offer(i);
}
}
while(!queue.isEmpty()) {
int temp = queue.poll();
numCourses--; //删除temp节点后，节点总数-1
for (int next : graph[temp]) {
inDegree[next] -= 1; //对应的节点的入度-1
if(inDegree[next] == 0) {
queue.offer(next);
}
}
}
return numCourses == 0; //判断是否把所有节点都删除了，是则代表无循环图，返回true
}
网友评论