图形序列化

Question

我正在寻找一个简单的算法来“序列化”有向图。特别是我有一组具有执行顺序相互依赖性的文件，并且我想在编译时找到正确的顺序。我知道这必须是一个相当普遍的事情 - 编译器一直在做 - 但是今天我的谷歌搜索能力很弱。这个“go-to”算法是什么？

- Kieron

Answer 1

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

在图论中，有向无环图的一个拓扑排序是其顶点的线性序列，在该序列中每个顶点都排在其所有后继的前面。每个 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)

- Andrew Peters

---

嗯...直接从维基百科复制的吗？ - Benjol

谢谢。这个方法帮助我理清了依赖树可以用这种方法进行排序的事实。 :-) - Shamasis Bhattacharya

Answer 2

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

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

有没有更好的解决方案？

- Kieron

---

不要使用foreach，而是使用while循环，维护两个指针遍历数据a，一个前导指针双步跳跃，一个后续指针单步跳跃。前导指针处理实际解析，如果它超过了后续指针，那么就存在一个循环。 - Tenderdude

Answer 3

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

- Giorgio

---

是的，如果一个图包含循环，那么无法进行拓扑排序。这与现实世界相对应：如果我要求你先做 A，然后又要求你先做 B，而又要求你先做 A，那你肯定无法满足我的要求 ;-). - sleske

Answer 4

我期望需要这种工具的程序可以以深度优先的方式遍历树，当它们到达叶子节点时，只需处理它（例如编译）并从图中删除它（或将其标记为已处理，并将所有叶子节点处理完毕的节点视为叶子节点）。

只要它是有向无环图，这种简单的基于堆栈的遍历应该很容易。

- Lily Ballard

---

是的，这就是你要做的。它被称为深度优先搜索（DFS）。除非你确定有一个有向无环图（DAG），否则必须检查后向边，否则循环将使你陷入无限循环。 - sleske