1+ // 207. 课程表
2+
3+
4+ /*
5+ 拓扑排序，广度优先搜索
6+ 1、入度数组 inDegree 记录每门课程的入度
7+ 2、邻接表 adjacent，key为课程号，value为依赖该课程的其他课程号数组
8+ 3、遍历先修课程数组 prerequisites，更新入度数组 inDegree 和邻接表 adjacent
9+ 4、队列 queue 存放入度为0的课程号，即没有先修课程，可以选修
10+ 5、从队列弹出课程号，表示该课程已修。然后获取已修课程的后继课程列表 successorList，更新所有后继课程的入度减1。
11+ 当后继课程入度为0时，则该课程可选修，将课程号存入队列。循环从队列弹出处理，直到没有可选修的课程
12+ 6、遍历入度数组 inDegree，判断所有课程号入度是否为0，不为0则不能修完所有课程，为0则能修完
13+
14+ 示例：n = 6，先决条件表：[[3, 0], [3, 1], [4, 1], [4, 2], [5, 3], [5, 4]]
15+ 课程 0, 1, 2 没有先修课，可以直接选。其余的课，都有两门先修课。
16+ 用有向图来展现这种依赖关系（做事情的先后关系），这种叫 有向无环图，把一个 有向无环图 转成 线性的排序 就叫 拓扑排序。
17+ 拓扑排序是将 有向无环图 所有顶点排成一个线性序列，使得图中任意一对顶点 u 和 v，若边 <u,v> ∈ E(G)，则 u 在线性序列中出现在 v 之前
18+ 有向图有 入度 和 出度 的概念：如果存在一条有向边 A --> B，则这条边给 A 增加了 1 个出度，给 B 增加了 1 个入度。
19+ 所以，顶点 0、1、2 的入度为 0，顶点 3、4、5 的入度为 2
20+ 拓扑排序过程：
21+ 1）先统计所有节点的入度
22+ 2）将入度为0的端点输出，删除该端点和该端点出发的有向边，并将后继端点入度减1
23+ 3）重复步骤2，如果最后有入度不为0的端点说明存在环，不存在拓扑排序，否则存在拓扑排序
24+
25+ 0
26+ ↘
27+ 3
28+ ↗ ↘
29+ 1 5 拓扑排序：0 1 2 3 4 5
30+ ↘ ↗
31+ 4
32+ ↗
33+ 2
34+ */
35+ class Solution {
36+ public boolean canFinish (int numCourses , int [][] prerequisites ) {
37+ Map <Integer , Integer > inDegree = new HashMap <>();
38+ for (int i = 0 ; i < numCourses ; i ++) {
39+ inDegree .put (i , 0 );
40+ }
41+ Map <Integer , List <Integer >> adjacent = new HashMap <>();
42+ for (int [] relate : prerequisites ) {
43+ int cur = relate [1 ];
44+ int next = relate [0 ];
45+ inDegree .put (next , inDegree .get (next ) + 1 );
46+ if (!adjacent .containsKey (cur )) {
47+ adjacent .put (cur , new ArrayList <>());
48+ }
49+ adjacent .get (cur ).add (next );
50+ }
51+ Queue <Integer > queue = new LinkedList <>();
52+ for (int key : inDegree .keySet ()) {
53+ if (inDegree .get (key ) == 0 ) {
54+ queue .offer (key );
55+ }
56+ }
57+ while (!queue .isEmpty ()) {
58+ int cur = queue .poll ();
59+ if (!adjacent .containsKey (cur )) {
60+ continue ;
61+ }
62+ List <Integer > successorList = adjacent .get (cur );
63+ for (int next : successorList ) {
64+ inDegree .put (next , inDegree .get (next ) - 1 );
65+ if (inDegree .get (next ) == 0 ) {
66+ queue .offer (next );
67+ }
68+ }
69+ }
70+ for (int key : inDegree .keySet ()) {
71+ if (inDegree .get (key ) != 0 ) {
72+ return false ;
73+ }
74+ }
75+ return true ;
76+ }
77+ }
0 commit comments