4
我有一组数据需要执行拓扑排序，有一些假设和约束条件，我想知道是否有人知道现有的适用于此的高效算法。拓扑分类变种算法
- 数据关系已知形成一个DAG（所以没有担心的周期）。
- 从A到B的边表示A依赖于B，所以B必须在拓扑排序中出现在A之前。
- 该图不一定是连接的;也就是说，对于任何两个节点N和M，可能无法通过跟随边缘从N到M（即使忽略边缘方向）。
- 数据关系是单独关联的。这意味着当存在从A指向B的边时，只有A节包含有关边的存在的信息。
该问题可以如下配制：
鉴于图形
G一组节点S的哪个可以或可以不具有入边，发现以下组成的子图G'的拓扑排序G中的所有节点都可从集合S（服从边缘方向）中的任何节点到达。
这混淆的常用方法拓扑排序，因为他们需要在集中的节点S没有任何入边，这是一件好事，是不是真的在我的情况。出现问题的情况是：
A --> B --> D
| ^ ^
| | |
\---> C ----/
哪里S = {B, C}。一个合适的排序是D, B, C，但如果一个正常的拓扑排序算法碰巧在C之前考虑B，它将以C, D, B结束，这是完全错误的。 （请注意，A不会出现在最终的排序，因为它不是来自S可达，它的出现给所有在S节点可能有入边的例子）
现在，我必须想象这是这是一个长期解决的问题，因为在一个安装命令中指定多个软件包时，这基本上就是像apt和yum这样的程序必须执行的操作。但是，当我搜索“依赖关系解析算法”这样的关键字句时，我得到的结果描述了正常的拓扑排序，这不能处理这种特殊情况。
我可以想到一些方法来做到这一点，但没有一个看起来特别优雅。我想知道是否有人有一些指向适当算法的指针，最好是能够在数据上一次操作的指针。
最终与此同时，尽管我仍然有兴趣知道是否有更好的和更少的暴力。 – 2010-07-24 04:14:25