46

我正在寻找一种简单的算法来“序列化”有向图。特别是我有一组文件，它们的执行顺序相互依赖，我想在编译时找到正确的顺序。我知道这一定是一件相当普遍的事情——编译器一直都在这样做——但我的 google-fu 今天一直很弱。什么是“首选”算法？

4

4 回答 4

63

拓扑排序（来自维基百科）：

在图论中，有向无环图 (DAG) 的拓扑排序或拓扑排序是其节点的线性排序，其中每个节点都位于其具有出站边的所有节点之前。每个 DAG 都有一个或多个拓扑排序。

伪代码：

L ← Empty list where we put the sorted elements
Q ← Set of all nodes with no incoming edges
while Q is non-empty do
    remove a node n from Q
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into Q
if graph has edges then
    output error message (graph has a cycle)
else 
    output message (proposed topologically sorted order: L)
于 2008-08-07T10:53:31.237 回答
1

我希望需要这个的工具只需以深度优先的方式遍历树，当它们碰到叶子时，只需处理它（例如编译）并将其从图中删除（或将其标记为已处理，并处理所有叶子的节点加工成叶子）。

只要它是一个 DAG，这个简单的基于堆栈的遍历应该是微不足道的。

于 2008-08-07T00:27:19.270 回答
1

我想出了一个相当幼稚的递归算法（伪代码）：

Map<Object, List<Object>> source; // map of each object to its dependency list
List<Object> dest; // destination list

function resolve(a):
    if (dest.contains(a)) return;
    foreach (b in source[a]):
        resolve(b);
    dest.add(a);

foreach (a in source):
    resolve(a);

最大的问题是它没有检测循环依赖的能力——它可以进入无限递归（即堆栈溢出；-p）。我能看到的唯一解决方法是将递归算法翻转为带有手动堆栈的交互式算法，并手动检查堆栈中是否存在重复元素。

有人有更好的吗？

于 2008-08-07T00:30:52.180 回答
1

如果图表包含循环，您的文件如何存在允许的执行顺序？在我看来，如果图形包含循环，那么您就没有解决方案，并且上述算法正确报告了这一点。

于 2009-01-23T15:09:27.690 回答