知识卡片

普通读书笔记卡 · 5654.d.1.f.3.u · 生成模型:未记录

拓扑排序让每条依赖向前

理解等级:中级

有向边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完成后头插代码完整实读;独立顶点和多解保留,不将线性序列当时间资源计划。 - 原始内容:拓扑排序 有些时候我们会遇到这一类问题:我们必须根据各种事件间的依赖关系来确定一种可接受的执行顺序。想象一下大学里那些需要满足一些先决条件才能选的课程,或者一个复杂的项目,其中某个特定的阶段必须在其他阶段开始之前完成。要为这一类问题建模,可以采用优先级图,其采用的是有向图的思路。在优先级图中,顶点代