知识卡片
拓扑输出前必须排除有向环
本章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)有