leetcode算法
(LeetCode- 207) 课程表
题目
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
1
2
3
| 输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
|
示例 2：
1
2
3
| 输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
|
分析
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| public class CourseSchedule {
public static void main(String[] args) {
int[][] prerequisites = {{1,0},{1,2},{0,2}};
int numCourses = 3;
boolean b = new CourseSchedule().canFinishDFS(numCourses, prerequisites);
System.out.println("");
}
/*广度优先遍历（基于入度表）实现*/
public boolean canFinish(int numCourses, int[][] prerequisites){
/*图的邻接表*/
List<List<Integer>> adjacencyList = new ArrayList<>();
for(int i = 0; i < numCourses; i++)
adjacencyList.add(new ArrayList<>());
/*入度表*/
int[] indegrees = new int[numCourses];
/*根据先修数组 prerequisites，初始化入度表和邻接表
* prerequisites[i] = [ai, bi]，表示要学习课程 ai则必须先学习课程 bi*/
for(int[] pre : prerequisites) {
/* 要注意有[ai, bi]，也可能会有 [ai, ci]，所以入度表要累加*/
indegrees[pre[0]]++;
/* 填充邻接表，表示顶点ai有一条由顶点bi指向顶点ai的边*/
adjacencyList.get(pre[1]).add(pre[0]);
}
/*队列用以存放入度为0的顶点*/
Queue<Integer> queue = new LinkedList<>();
/*初始化队列*/
for(int i = 0; i < numCourses; i++)
if(indegrees[i] == 0) queue.add(i);
while(!queue.isEmpty()) {
/*从队列中取得一个入度为0的顶点，顶点计数同时减一*/
int vertex = queue.poll();
numCourses--;
/*从邻接表中获得当前顶点vertex所指向的顶点 indication，
* 并将indication的值减一，如果indegrees[indication]为0，
* 说明 indication 所有的前驱节点已经被处理过 ，则将indication也放入队列*/
for(int indication : adjacencyList.get(vertex))
if(--indegrees[indication] == 0) queue.add(indication);
}
/*整个课程可以安排成功，则图是有向无环图，则所有节点都入队并出队后，就完成了拓扑排序，
* 若课程安排图中存在环，一定有节点的入度始终不为0，会被重复处理
* 所以成功拓扑排序，出队次数等于课程个数，检查 numCourses == 0 即可判断课程是否可以成功安排*/
return numCourses == 0;
}
/*深度优先遍历（基于出度表）实现*/
public boolean canFinishDFS(int numCourses, int[][] prerequisites) {
/*图的邻接表*/
List<List<Integer>> adjacencyList = new ArrayList<>();
for(int i = 0; i < numCourses; i++)
adjacencyList.add(new ArrayList<>());
for(int[] cp : prerequisites)
adjacencyList.get(cp[1]).add(cp[0]);
/*用flags存放每个节点 i（课程）的状态：
初始未被访问： flag[i] == 0；
从当前节点开始 DFS 访问：flag[i] == 1；
当前节点完成 DFS 访问：flag[i] == -1 。*/
int[] flags = new int[numCourses];
for(int i = 0; i < numCourses; i++)
if(!dfsVertex(adjacencyList, flags, i)) return false;
return true;
}
/*从当前顶点i开始进行深度遍历*/
private boolean dfsVertex(List<List<Integer>> adjacency, int[] flags, int i) {
/* 深度遍历中节点 i 被第 2 次访问，说明图有环，直接返回 False*/
if(flags[i] == 1) return false;
/*当前访问节点已经处理过了，无需再重复搜索，直接返回 True*/
if(flags[i] == -1) return true;
/*标记flag[i]，从当前节点开始采用递归进行邻接顶点访问*/
flags[i] = 1;
for(Integer j : adjacency.get(i))
if(!dfsVertex(adjacency, flags, j)) return false;
/*当前节点完成 DFS 访问，访问过程中没有环，返回false*/
flags[i] = -1;
return true;
}
}
|