【python-leetcode207-拓扑排序】课程表

【python-leetcode207-拓扑排序】课程表,第1张

概述你这个学期必须选修 numCourse 门课程,记为 0 到 numCourse-1 。 在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要

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

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

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

 

示例 1:

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

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

提示:

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

 

思路:我们先转换一下。对于[1,0]:意思是要想学1课程,必须先学完0课程,以有向图表示就是0->1,以此类推。接下来记录每一个课程的入度,由于有0->1,因此1课程的入度加1。再记录每一个课程学完之后可以继续学的课程(最近),则有0:[1],即学完0课程之后可以学习1课程。接下来我们用一个队列queue来存储所有入度为0的课程。

方法一:使用广度优先遍历

from collections import dequeclass Solution:    def canFinish(self,numCourses,prerequisites):         @H_403_48@#用于记录每一个元素的入度        indegrees=[0 for _ in range(numCourses)]        用于记录每一个元素的连接元素(当前元素为首)        adjacency=[[]  range(numCourses)]        queue = deque()         Get the indegree and adjacency of every course.        for cur,pre  prerequisites:            indegrees[cur] += 1            adjacency[pre].append(cur)         Get all the courses with the indegree of 0.        for i  range(len(indegrees)):            if not indegrees[i]:                 queue.append(i)         BFS topSort.        print(indegrees)        (adjacency)        (queue)        while queue:            pre = queue.popleft()            numCourses -= 1            for cur  adjacency[pre]:                indegrees[cur] -= 1                 indegrees[cur]:                     queue.append(cur)        return  numCoursess=Solution()print(s.canFinish(6,[2,3],[4,5],4],[5,1]]))        

[0,1,2,1]
[[1],[5],[],[2],[4]]
deque([0,3])

如果最终还存在课程学不了,则返回False,否则返回True

方法二:深度优先遍历

原理是通过 DFS 判断图中是否有环。

算法流程:

1.借助一个标志列表 flags,用于判断每个节点 i (课程)的状态:

未被 DFS 访问:i = 0;已被其他节点启动的 DFS 访问:i = -1;已被当前节点启动的 DFS 访问:i = 1。

2.对 numCourses 个节点依次执行 DFS,判断每个节点起步 DFS 是否存在环,若存在环直接返回 False。

DFS 流程;
(1)终止条件:

当 flag[i] == -1,说明当前访问节点已被其他节点启动的 DFS 访问,无需再重复搜索,直接返回 True。当 flag[i] == 1,说明在本轮 DFS 搜索中节点 i 被第 2 次访问,即 课程安排图有环 ,直接返回 False。

(2)将当前访问节点 i 对应 flag[i] 置 1,即标记其被本轮 DFS 访问过;
(3)递归访问当前节点 i 的所有邻接节点 j,当发现环直接返回 False;
(4)当前节点所有邻接节点已被遍历,并没有发现环,则将当前节点 flag 置为 -1并返回 True。
3.若整个图 DFS 结束并未发现环,返回 True。

def canFinish(self,numCourses: int,prerequisites: List[List[int]]) -> bool:         dfs(i,adjacency,flags):            if flags[i] == -1: return True            if flags[i] == 1:  False            flags[i] = 1            for j  adjacency[i]:                not dfs(j,flags):  False            flags[i] = -1             True        adjacency = [[]  range(numCourses)]        flags = [0  prerequisites:            adjacency[pre].append(cur)         range(numCourses):             False        return True

 

参考链接:https://leetcode-cn.com/problems/course-schedule/solution/course-schedule-tuo-bu-pai-xu-bfsdfsliang-chong-fa/

总结

以上是内存溢出为你收集整理的【python-leetcode207-拓扑排序课程表全部内容,希望文章能够帮你解决【python-leetcode207-拓扑排序】课程表所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/1190046.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-03
下一篇 2022-06-03

发表评论

登录后才能评论

评论列表(0条)

保存