我有一组数据，我需要执行拓扑排序，有一些假设和约束，我想知道是否有人知道一个适合于此的现有的，有效的算法 .
-
已知数据关系形成DAG（因此无需担心周期） .
-
从A到B的边表示A依赖于B，因此B必须在拓扑排序中出现在A之前 .
-
图表未必连接;也就是说，对于任何两个节点N和M，可能无法通过跟随边缘从N到M（即使忽略边缘方向） .
-
数据关系是单独链接的 . 这意味着当存在从A到B的边缘时，只有A节点包含有关边缘存在的信息 .
问题可以表述如下：
给定图G中的一组节点S，其可能有也可能没有入边，找到子集G'的拓扑排序，该子集G'由G中的所有节点组成，可从集合S中的任何节点（服从边缘方向）到达 .
这会混淆拓扑排序的常用方法，因为它们要求set S 中的节点没有任何传入边缘，这在我的情况下是不正确的 . 病理案例是：
A --> B --> D
| ^ ^
| | |
\---> C ----/
哪里 S = {B, C} . 一个合适的顺序是 D, B, C ，但是如果正常的拓扑排序算法碰巧在 C 之前考虑 B ，那么最终会得到 C, D, B ，这是完全错误的 . （注意 A 没有出现在结果排序中，因为它不能从 S 到达;它是一个例子，其中 S 中的所有节点都可能有传入边缘）
现在，我必须想象这是一个长期解决的问题，因为当你在一个安装命令中指定多个包时，这基本上就像 apt 和 yum 这样的程序 . 但是，当我搜索像"dependency resolution algorithm"这样的关键短语时，我得到的结果描述了正常的拓扑排序，它没有处理这种特殊情况 .
我可以想到几种方法来做到这一点，但它们中没有一个看起来特别优雅 . 我想知道是否有人有一些指向适当算法的指针，最好是一个可以在数据上单次操作的指针 .
2 回答
我不认为你会发现一个算法可以通过一次数据传递来做到这一点 . 我将执行广度优先搜索，从S中的节点开始，然后对结果子图进行拓扑排序 .
我认为你可以对整个图进行拓扑排序，然后只选择可以从节点集中到达的节点（你可以从集合中的节点进行一些深度优先搜索，按排序后得到的顺序，以及如果以前没有访问过节点，你将进入节点的子树 .