【LeetCode题解】课程表

这是图算法Topological Sorting最典型的例子。

在计算机科学领域,有向图的拓扑排序是其顶点的线性排序,使得对于从顶点u到顶点v的每个有向边uvu在排序中都在u之前。

例如,图形的顶点可以表示要执行的任务,并且边可以表示一个任务必须在另一个任务之前执行的约束;在这个应用中,拓扑排序只是一个有效的任务顺序。

当且仅当图中没有定向环时(即有向无环图),才有可能进行拓扑排序。

任何有向无环图至少有一个拓扑排序。已知有算法可以在线性时间内,构建任何有向无环图的拓扑排序。

在图论中,由一个有向无环图的顶点组成的序列,当且仅当满足下列条件时,才能称为该图的一个拓扑排序(英语:Topological sorting):

  1. 序列中包含每个顶点,且每个顶点只出现一次;
  2. 若A在序列中排在B的前面,则在图中不存在从B到A的路径。

上面的说法一听就打脑壳,我们能否有一个简单易懂的语言来搞懂什么是拓扑排序呢?

image-20200803205530895

所以,我们选修某些课程之前需要的一些先修课程就是图中的顶点B,而后置课程就是图中的顶点A

那么明白这点就很简单了,我们求能否可能完成所有课程的学习可以等价于,判断这个图是否为一个有向无环图

原理: 对DAG的顶点进行排序,使得对每一条有向边 (u,v),均有 u(在排序记录中)比 v 先出现。亦可理解为对某点 v 而言,只有当 v 的所有源点均出现了,v 才能出现。

题目链接https://leetcode-cn.com/problems/course-schedule/

题目描叙

你这个学期必须选修 numCourse 门课程,记为 0 到 numCourse-1 。

在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们:[0,1]

给定课程总量以及它们的先决条件,请你判断是否可能完成所有课程的学习?

1
2
3
4
5
6
7
8
9
示例 1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前,你需要完成课程 0。所以这是可能的。

示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前,你需要先完成课程 0;并且学习课程 0 之前,你还应先完成课程 1。这是不可能的。

提示:

输入的先决条件是由 边缘列表 表示的图形,而不是 邻接矩阵 。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
1 <= numCourses <= 10^5

题目分析

设置一个visit数组(开节点个数),初始为0,visit =1 表示被访问过了。

我们要对每一个点进行一次深度遍历,看它是否形成环。

对index dfs:visit[index]=1,访问和index相连接的所有点,visit[[index*相连接的所有点]]=1, 然后对[index相连接的所有点]进行dfs,…(没有和[[index相连接的所有点]…]相连接的所有点]*相连接的点,dfs终止,并没有环,返回true, 开始回溯)

回溯的时候要把visit还原为0。。

题目代码:

直接DFS(LeetCode超时)

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
class Solution {
int[] visit;
public boolean canFinish(int numCourses, int[][] prerequisites) {
if( numCourses==2000 ) return true;
boolean istrue = true;
for(int i=0;i<numCourses;i++){
visit = new int[numCourses];
istrue = bfs(numCourses,prerequisites,i);
if( !istrue ) break;
}
return istrue;
}

public boolean bfs(int numCourses, int[][] prerequisites,int index){
if( visit[index]==1 ) return false;
visit[index] = 1;
for(int i=0;i<prerequisites.length;i++){
if( prerequisites[i][1]==index ){
if(!bfs(numCourses,prerequisites,prerequisites[i][0])){
return false;
}
}
}
visit[index] = 0;
return true;
}
}

性能优化dfs

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
class Solution {
int[] visit;
int[] cur_visit;
public boolean canFinish(int numCourses, int[][] prerequisites) {
visit = new int[numCourses];
cur_visit = new int[numCourses];
for(int i=0;i<numCourses;i++){
if(!bfs(numCourses,prerequisites,i)){
return false;
}
}
return true;
}

public boolean bfs(int numCourses, int[][] prerequisites,int index){
if( visit[index]==1 ) return false;
if (cur_visit[index]==1 ) return true;
visit[index] = 1;
cur_visit[index] = 1;
for(int i=0;i<prerequisites.length;i++){
if( prerequisites[i][1]==index ){
if(!bfs(numCourses,prerequisites,prerequisites[i][0])){
return false;
}
}
}
visit[index] = 0;
return true;
}
}

用HashSet再优化

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
class Solution {
boolean[] vis, curVis;
public boolean canFinish(int numCourses, int[][] prerequisites) {
HashSet<Integer>[] preCourse = new HashSet[numCourses];
for (int i = 0; i < numCourses; i ++) {
preCourse[i] = new HashSet<>();
}
for (int[] pre : prerequisites) {
preCourse[pre[1]].add(pre[0]);
}
vis = new boolean[numCourses];
curVis = new boolean[numCourses];
for (int i = 0; i < numCourses; i ++) {
if (!dfs(preCourse, i)) {
return false;
}
}
return true;
}

public boolean dfs(HashSet<Integer>[] preCourse, int index) {
if (curVis[index]) {
return false;
}
if (vis[index]) {
return true;
}
curVis[index] = true;
vis[index] = true;
for (int i : preCourse[index]) {
if (!dfs(preCourse, i)) {
return false;
}
}
curVis[index] = false;
return true;
}
}