php网站程序怎么安装,南宁网站建设服务,制作网站可以赚钱吗,像那种代刷网站怎么做题目 你这个学期必须选修numCourses门课程#xff0c;记为0到numCourses - 1。在选修某些课程之前#xff0c;需要一些先修课程。先修课程按数组prerequisites给出#xff0c;其中prerequisites[i] [ai, bi]#xff0c;表示如果要学习课程ai#xff0c;则必须先学习课程b…题目 你这个学期必须选修numCourses门课程记为0到numCourses - 1。在选修某些课程之前需要一些先修课程。先修课程按数组prerequisites给出其中prerequisites[i] [ai, bi]表示如果要学习课程ai则必须先学习课程bi。比如先修课程对[0, 1]表示想要学习课程0你需要先完成课程1。 请你判断是否可能完成所有课程的学习如果可以返回true。否则返回false。 备注prerequisites[i]中的所有课程对互不相同。 示例 1
输入numCourses 2, prerequisites [[1,0]]
输出true
解释总共有2门课程。学习课程1之前你需要完成课程0。
这是可能的。 示例 2
输入numCourses 2, prerequisites [[1,0], [0,1]]
输出false
解释总共有2门课程。学习课程1之前你需要先完成课程0并且学习课程0之前还应先完成课程1。
这是不可能的。 深度优先搜索算法 这个问题描述了一个典型的图论问题涉及到课程之间的依赖关系。要判断是否有可能完成所有课程的学习我们需要检查是否存在环。如果有环存在则意味着某些课程之间形成了一个闭环依赖从而无法完成所有课程的学习。 深度优先搜索算法DFS是解决本问题的一种有效方法可用于检测图中是否存在环。其基本思想为使用DFS来遍历图中的所有节点在遍历过程中我们需要标记正在访问的节点以检测环的存在如果在访问过程中遇到一个已经在访问路径上的节点那么就找到了一个环。如果所有节点都能被访问且没有环则表示可以完成所有课程的学习。使用深度优先搜索算法求解本题的主要步骤如下。 1、构建一个邻接表来表示图结构。 2、对于每个节点执行DFS并跟踪正在访问的节点。 3、如果在访问过程中遇到已经存在于当前路径上的节点则存在环。 4、如果所有节点都被访问过且没有发现环则返回true。否则返回false。 根据上面的算法步骤我们可以得出下面的示例代码。
def course_schedule_by_dfs(numCourses, prerequisites):def dfs(course, visiting):if visiting[course]:return Falseif visited[course]:return True# 标记当前节点正在访问visiting[course] Truefor next_course in graph[course]:if not dfs(next_course, visiting):return False# 结束访问visiting[course] False# 标记当前节点已被访问visited[course] Truereturn True# 构建邻接表graph [[] for _ in range(numCourses)]# 标记每个节点是否被访问过visited [False] * numCourses# 标记每个节点是否正在访问visiting [False] * numCourses# 填充邻接表for course, prereq in prerequisites:graph[prereq].append(course)# 对于每个节点执行DFSfor course in range(numCourses):if not dfs(course, visiting):return Falsereturn TruenumCourses 2
prerequisites [[1, 0]]
print(course_schedule_by_dfs(numCourses, prerequisites))numCourses 2
prerequisites [[1, 0], [0, 1]]
print(course_schedule_by_dfs(numCourses, prerequisites)) 拓扑排序法 拓扑排序法是针对有向无环图 (DAG) 的一种排序方法它将图中的所有顶点按照某种顺序排列使得对于每条有向边u → v顶点u在顶点v之前出现。如果一个图可以进行拓扑排序则说明该图没有环。如果在排序过程中发现某个顶点的入度永远不能变为 0则说明存在环。使用拓扑排序法求解本题的主要步骤如下。 1、构建一个邻接表来表示图结构。 2、计算每个节点的入度即有多少条边指向该节点。 3、将所有入度为0的节点加入队列。 4、从队列中取出节点将其添加到结果列表中并减少其相邻节点的入度。 5、将入度变为0的节点加入队列。 6、重复步骤4和5直到队列为空。 7、如果所有节点都被处理则不存在环。否则存在环。 根据上面的算法步骤我们可以得出下面的示例代码。
from collections import dequedef course_schedule_by_topsort(numCourses, prerequisites):# 构建邻接表graph [[] for _ in range(numCourses)]# 计算每个节点的入度indegrees [0] * numCourses# 填充邻接表并计算入度for course, prereq in prerequisites:graph[prereq].append(course)indegrees[course] 1# 创建队列将所有入度为0的节点加入队列queue deque([node for node in range(numCourses) if indegrees[node] 0])# 存储已完成的课程completed_courses []# 处理队列中的节点while queue:prereq queue.popleft()completed_courses.append(prereq)for course in graph[prereq]:indegrees[course] - 1if indegrees[course] 0:queue.append(course)# 如果所有课程都被完成则返回Truereturn len(completed_courses) numCoursesnumCourses 2
prerequisites [[1, 0]]
print(course_schedule_by_topsort(numCourses, prerequisites))numCourses 2
prerequisites [[1, 0], [0, 1]]
print(course_schedule_by_topsort(numCourses, prerequisites)) 总结 使用深度优先搜索算法求解本题的时间复杂度为O(V E)。其中V是顶点的数量课程总数E是边的数量先修课程对的数量每个顶点和每条边都会被访问一次。最坏情况下递归栈的深度可以达到 V因此空间复杂度为O(V)。深度优先搜索算法的优点是实现相对简单但对于大规模数据集递归可能导致栈溢出。 拓扑排序法的时间复杂度也为O(V E)最坏情况下的空间复杂度为O(V E)因为其需要额外的空间来存储邻接表和队列。拓扑排序法的优点是实现较为直观易于理解但实现稍微复杂一些需要额外的入度计数和队列操作。
