企业建设网站目的,比较有名的编程培训机构,阿里巴巴网页版,wordpress数据搬移目录
1 基础知识
1.1 什么是拓扑排序
1.2 如何进行拓扑排序
1.3 拓扑排序举例
2 207. 课程表
3 210. 课程表 II 菜鸟做题#xff0c;语言是 C 1 基础知识
1.1 什么是拓扑排序
含义#xff1a;根据节点之间的依赖关系来生成一个有序的序列。
应用#xff1a…目录
1 基础知识
1.1 什么是拓扑排序
1.2 如何进行拓扑排序
1.3 拓扑排序举例
2 207. 课程表
3 210. 课程表 II 菜鸟做题语言是 C 1 基础知识
1.1 什么是拓扑排序
含义根据节点之间的依赖关系来生成一个有序的序列。
应用
在项目管理中按照任务之间的的依赖关系来安排执行顺序。在编译原理中按照编译单元的依赖关系来确定编译单元的生成顺序。在程序设计中按照模块之间的依赖关系来确定模块的加载和执行顺序。 突然想起来好像在操作系统原理里学过 1.2 如何进行拓扑排序
排序步骤
选择入度为 0 的节点加入到排序结果中并从图中移除该节点以及它的所有出边重复步骤 1每次都选择入度为 0 的节点加入到排序结果中并更新图中剩余节点的入度重复步骤 1 和 2直到所有的节点都被加入到排序结果中或者不再存在入度为 0 的节点。
名词解释
→ 节点 属于节点的 入边节点 → 属于节点的 出边 如果图中不再存在入度为 0 的节点且并非所有的节点都被加入到排序结果中那么说明原图中存在环。综上拓扑排序的主要功能是帮助安排顺序顺带帮助检测图中有没有环。 1.3 拓扑排序举例
下图描述了一个拓扑排序过程。
① 入度为 0 的节点有 B、D我们任意选择 B并删除它的出边 ② 入度为 0 的节点有 A、D我们任意选择 A并删除它的出边更新后入度为 0 的节点有 C、D我们任意选择 C并删除它的出边 ③ 入度为 0 的节点有 D我们选择 D并删除它的出边更新后入度为 0 的节点有 F我们选择 F并删除它的出边 以此类推不再赘述。通过 “任意选择” 一词可以看出拓扑排序的结果不止一种。 2 207. 课程表
感觉解题方法和拓扑排序关系不大更多的是从题意出发想了很久要怎么才能把思路表述清楚最终认为还是看代码来得快 TT
解题思路假设有先修课程对 [01] 和 [02]
初始化获取每门课程的先修课程数组比如0 对应 [12]初始化设置记录访问状态的数组并将访问状态全部置为 0循环访问每门课程判断它的先修课程是否已经被全部修完如果它的先修课程未被全部修完则表明无法完成所有课程的学习
访问状态
visited[course] 0该门课程还未被学习visited[course] 1该门课程正在被学习visited[course] 2该门课程已经被学习 针对 “该门课程正在被学习” 的说法需要说明的是这是算法题而不是现实生活如果一门课正在被学习不是代表学习它需要一段时间而是代表它的先修课程不可能被修完导致我们永远学不了它。 class Solution {
public:vectorint visited;vectorvectorint mustFinish;bool possible true;void helper(int course) {// 指明该门课程正在被学习visited[course] 1;// 判断其先修课程是否已被修完for (auto preCourse : mustFinish[course]) {// 递归访问未被学习的先修课程if (visited[preCourse] 0) {helper(preCourse);if (!possible) return;// 先修课程正在被学习因为卡住了} else if (visited[preCourse] 1) {possible false;return;}}// 指明该门课程已经被学习visited[course] 2;}bool canFinish(int numCourses, vectorvectorint prerequisites) {visited.resize(numCourses);mustFinish.resize(numCourses);// 获取每门课程的先修课程数组for (auto p : prerequisites) {mustFinish[p[0]].push_back(p[1]);}// 循环访问每门课程for (int i 0; i numCourses possible; i) {helper(i);}return possible;}
}; 3 210. 课程表 II
在 207. 课程表 的基础上增加一个数据结构来存储课程顺序即可。
唯一区别在于
for (int i 0; i numCourses possible !visited[i]; i) 新增条件 !visited[i]不允许已经被访问过的课程再被访问避免了课程重复被学习。 class Solution {
public:vectorint visited;vectorvectorint mustFinish;bool possible true;vectorint ans;void helper(int course) {visited[course] 1;for (auto preCourse : mustFinish[course]) {if (visited[preCourse] 0) {helper(preCourse);if (!possible) return;} else if (visited[preCourse] 1) {possible false;return;}}visited[course] 2;ans.push_back(course);}vectorint findOrder(int numCourses, vectorvectorint prerequisites) {visited.resize(numCourses);mustFinish.resize(numCourses);for (auto p : prerequisites) {mustFinish[p[0]].push_back(p[1]);}for (int i 0; i numCourses possible !visited[i]; i) {helper(i);}if (possible) return ans;return {};}
};
