题目
你这个学期必须选修
numCourse
门课程,记为0
到numCourse-1
。在选修某些课程之前需要一些先修课程。 例如,想要学习课程
0
,你需要先完成课程1
,我们用一个匹配来表示他们:[0,1]
给定课程总量以及它们的先决条件,请你判断是否可能完成所有课程的学习?
示例 1:
1
2
3 输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前,你需要完成课程 0。所以这是可能的。示例 2:
1
2
3 输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前,你需要先完成课程 0;并且学习课程 0 之前,你还应先完成课程 1。这是不可能的。提示:
- 输入的先决条件是由 边缘列表 表示的图形,而不是 邻接矩阵 。详情请参见图的表示法。
- 你可以假定输入的先决条件中没有重复的边。
1 <= numCourses <= 10^5
1
2
3 >来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/course-schedule
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
- 审题,是否可能完成所有课程的学习,就是判断这个Digraph有没有directed circle,如果有就不可能,也就是判断这个图是不是DAG(Directed acyclic Graph),如果是,就可能完成。这是一道topological sort。
- 如何判断?
假设对vertexv
做DFS,递归过程中调用了dfs(v)
,那么说明不是DAG,换句话说如果DFS这个图,且有v->w
,那w
在v
直接输出。
实现
canFinish()
函数第一个形参为vertex数量,第二个形参为edges list;- 需要一个容器记录vertex是否已经访问过;
- 需要一个bag记录先调用DFS的vertex,一次DFS中v同一个vertex重复出现时返回false;
- 需要注意图中可能有多个Connected Components,需要循环DFS;
- 空间换时间,避免重复搜索
edges list
,需要转换为adjency list
; - 如果一个vertex没有任何adjacency,那么它不可能出现在任何cycle中,应当从查重的set中删除;
- DFS一个vertex之后要把该节点从查重列表中删除;
代码如下:
1 | class Solution { |
其他方法
拓扑排序(入度表+BFS)
其核心思想是从前向后进行拓扑排序,因为拓扑排序的起点总是入度为0的。而能够进行拓扑排序的图一定是DAG,如果拓扑排序结束,图中还有剩下的vertices,那么该图不是DAG。
- 首先统计每个节点的入度,生成入度表;
- 由于入度为0的节点一定是拓扑结构的起点,那么需要依次处理这些起点节点。使用队列管理等待处理的节点,当前处理的节点出队,其拓扑的下个节点入度
-1
表示把当前节点从图中“删除”;如果下个结点的入度此时也为0,就把下个节点入队等待处理; - 由于节点不重复,每“删除”一个节点,就更新当前节点数目;如果Directed cycle存在,那么最终一定会有无法被”删除“的节点。
代码如下:
1 | class Solution { |
时间复杂度O(V+E)
,遍历一个图需要访问所有节点和临边;
空间复杂度O(V+E)
,为邻接表的大小。