图序列化
我正在寻找一个简单的algorithm来“序列化”一个有向图。 特别是我有一组文件，它们的执行顺序有相互依赖关系，我想在编译时find正确的顺序。 我知道这一定是一件相当普通的事情 – 编译器一直都在做 – 但是我的google-fu今天一直很弱。 什么是'去'的algorithm呢？
拓扑sorting （来自Wikipedia）：
在图论中，有向无环图（DAG）的拓扑sorting或拓扑sorting是其节点的线性sorting，其中每个节点位于具有出站边缘的所有节点之前。 每个DAG都有一个或多个拓扑sorting。
伪代码：
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) 我期望的工具只需要以深度优先的方式遍历树，当它们碰到树叶时，只需处理它（例如编译）并将其从图中移除（或将其标记为已处理，并将所有叶作为叶子处理）。
只要它是一个DAG，这个简单的基于栈的步行应该是微不足道的。
如果graphics包含循环，那么您的文件如何存在允许的执行顺序？ 在我看来，如果graphics包含循环，那么你就没有解决scheme，并且上述algorithm正确地报告了这一点。
我想出了一个相当幼稚的recursionalgorithm（伪代码）：
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);
最大的问题是它没有能力检测循环依赖 – 它可以进入无限recursion（即堆栈溢出; -p）。 我可以看到的唯一方法是将recursionalgorithm转换为手动堆栈的迭代algorithm，并手动检查堆栈中的重复元素。
任何人有更好的东西？
