力扣：207.课程表 |
您所在的位置：网站首页 › 课程表排序算法有哪些方法 › 力扣：207.课程表 |
力扣：207.课程表
|
力扣：207.课程表——拓扑排序算法
1. 题目描述
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。 示例 1： 输入：numCourses = 2, prerequisites = [[1,0]] 输出：true 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。 示例 2： 输入：numCourses = 2, prerequisites = [[1,0],[0,1]] 输出：false 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。 提示： 1 if(inDegree[i] == 0){ q.push(i); } } 逐个输出入度为0的节点（此处为计算输出节点的个数），同时将该顶点的指向的顶点的入度减1，并判断减1后是否有新的入度为0的节点产生，若有则入队，否则跳过； while(!q.empty()){ int top = q.front(); q.pop(); sum++; for(int i = 0; i q.push(node); } } }完整代码如下： class Solution { public: bool canFinish(int numCourses, vector& prerequisites) { vector inDegree(numCourses,0); vector graph(numCourses); for(auto edge : prerequisites){ int i = edge[0]; int j = edge[1]; graph[i].push_back(j); inDegree[j]++; } queue q; int sum = 0; for(int i = 0; i q.push(i); } } while(!q.empty()){ int top = q.front(); q.pop(); sum++; for(int i = 0; i q.push(node); } } } return sum == numCourses; } };以上的代码为邻接表解法。 以下为邻接矩阵解法，效率过低。 class Solution { public: bool canFinish(int numCourses, vector& prerequisites) { vector inDegree(numCourses,0); vector graph(numCourses,vector(numCourses,0)); for(auto edge : prerequisites){ int i = edge[0]; int j = edge[1]; graph[i][j] = 1; inDegree[j]++; } queue q; int sum = 0; for(int i = 0; i q.push(i); } } while(!q.empty()){ int top = q.front(); q.pop(); sum++; for(int i = 0; i inDegree[i]--; if(inDegree[i] == 0){ q.push(i); } } } } return sum == numCourses; } };临界矩阵解法效率都为5%，邻接表和邻接矩阵对比如下，第1、2为邻接表，后两个为邻接矩阵。
|
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |