知识卡片

问题卡 · 5654.d.1.f.3.v · 生成模型:未记录

拓扑输出前必须排除有向环

理解等级:中级

本章dfs_main发现白邻居才递归,遇灰色邻居却直接忽略,没有据此报告环;完成时仍头插ordered。于是输入含有向环时,它也可能返回0并给出一个列表,但列表不可能满足环上全部先后依赖。

在有向DFS中,指向仍在探索的灰色祖先意味着回边,是环的证据。若函数职责是拓扑排序,就应验证DAG前提或检测这种回边并返回清楚的失败,而不能用“搜索没有内部错误”代替“得到了合法拓扑序”。

这里指出原实现的前置条件与缺失验证,不声称已改代码/测试。0仅说明其现有遍历/链表操作完成,DAG仍需调用方保证。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      有向无环图,它表示7门课程及其先决条件组成的一份课程表:CS100没有先决条件,CS200需要CS100,CS300需要CS200和MA100,MA100没有先决条件,MA200需要MA100,MA300需要CS300和MA200,并且CS150没有先决条件同时也不是先决条件。 图 11-9 a)有

    参考来源

    - 位置:《算法精解:C语言描述》第11章《关于图的应用举例:拓扑排序》(spine1333;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1300.html;u200-ch11-023)。 - 结论依据:200明确DAG前提与02947完整邻居颜色分支实读:只处理white,未有gray失败逻辑;02948公开函数return0,不从完成列表推断拓扑合法。 - 原始内容:有向无环图,它表示7门课程及其先决条件组成的一份课程表:CS100没有先决条件,CS200需要CS100,CS300需要CS200和MA100,MA100没有先决条件,MA200需要MA100,MA300需要CS300和MA200,并且CS150没有先决条件同时也不是先决条件。 图 11-9 a)有