我有一组数据，我需要对其执行拓扑排序，并带有一些假设和约束，我想知道是否有人知道适用于此的现有有效算法。
- 已知数据关系会形成 DAG（因此无需担心循环）。
- 从 A 到 B 的边表明 A 依赖于 B，因此 B 在拓扑排序中必须出现在 A 之前。
- 图不一定是连通的；也就是说，对于任何两个节点 N 和 M，可能无法通过沿边从 N 到 M（即使您忽略边方向）。
- 数据关系是单独链接的。这意味着当存在从 A 指向 B 的边时，只有 A 节点包含有关边存在的信息。
问题可以表述如下：
S给定图G中可能有也可能没有传入边的一组节点，找到子图的拓扑排序，该子图G'由集合中G的任何节点可到达的所有节点组成S（服从边方向）。
这混淆了拓扑排序的常用方法，因为它们要求集合中的节点S没有任何传入边，这在我的情况下是不正确的。病理情况是：
A --> B --> D
| ^ ^
| | |
\---> C ----/
哪里S = {B, C}。一个合适的排序应该是D, B, C，但是如果一个正常的拓扑排序算法之前碰巧考虑B过C，它最终会C, D, B是 ，这是完全错误的。（请注意，A它不会出现在结果排序中，因为它无法从 到达S；它在那里给出了一个示例，其中所有节点都S可能具有传入边）
现在，我不得不想象这是一个长期解决的问题，因为这本质上是程序喜欢apt并且yum在一个安装命令中指定多个包时必须做的事情。但是，当我搜索“依赖解析算法”之类的关键词时，我得到的结果描述了正常的拓扑排序，它不能处理这种特殊情况。
我可以想到几种方法来做到这一点，但没有一种方法看起来特别优雅。我想知道是否有人有一些指向适当算法的指针，最好是可以在数据上一次通过的算法。