图序列化

Question

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

Answer 1

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

在图理论中，有向无环图（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)

Answer 2

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

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

Answer 3

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

Answer 4

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

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）。我能看到的唯一解决方法是将递归算法翻转为具有手动堆栈的交互式算法，并手动检查堆栈中是否有重复元素。

有人有更好的东西吗？