知识卡片
拓扑排序让每条依赖向前
有向边u→v表示u必须先于v,拓扑排序给全部顶点一个线性次序,使每条边的起点都在终点之前。它适用于有向无环图;有环意味着这一组前置条件无法同时满足。
02945课程例可按CS100、CS200、MA100、CS300、MA200、MA300、CS150排列,所有先修边向前;独立CS150可放其他位置,所以合法次序通常不唯一。拓扑排序不是把图“变成DAG”,而是在已有DAG上找线性次序。
DFS在完成一个顶点全部后继后将它放到结果头部,等价于逆完成顺序。在DAG前提下,边u→v的后继v会先完成或早已完成,因此结果中u先于v;整个图还需外层检查所有白色顶点。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
拓扑排序 有些时候我们会遇到这一类问题:我们必须根据各种事件间的依赖关系来确定一种可接受的执行顺序。想象一下大学里那些需要满足一些先决条件才能选的课程,或者一个复杂的项目,其中某个特定的阶段必须在其他阶段开始之前完成。要为这一类问题建模,可以采用优先级图,其采用的是有向图的思路。在优先级图中,顶点代
参考来源
- 位置:《算法精解:C语言描述》第11章《关于图的应用举例:拓扑排序》(spine1333;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1300.html;u200-ch11-022)。
- 结论依据:200拓扑定义、课程全部约束与02945双图、02947–02948完成后头插代码完整实读;独立顶点和多解保留,不将线性序列当时间资源计划。
- 原始内容:拓扑排序 有些时候我们会遇到这一类问题:我们必须根据各种事件间的依赖关系来确定一种可接受的执行顺序。想象一下大学里那些需要满足一些先决条件才能选的课程,或者一个复杂的项目,其中某个特定的阶段必须在其他阶段开始之前完成。要为这一类问题建模,可以采用优先级图,其采用的是有向图的思路。在优先级图中,顶点代