图序列化

我正在寻找一种简单的算法来“序列化”有向图。特别是我有一组相互依赖于执行顺序的文件,我想在编译时找到正确的顺序。我知道这一定是一件相当普通的事情 - 编译器一直都在做 - 但我的google-fu今天一直很弱。什么是'去'算法呢?

0

3 答案

我想出了一个相当幼稚的递归算法(伪代码):

Map> source; // map of each object to its dependency list List 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)。我可以看到的唯一方法是将递归算法转换为手动堆栈的迭代算法,并手动检查堆栈中重复的元素。

任何人有更好的东西?

0
额外
而不是一个foreach使用一段时间,保持两个指针遍历数据a,一个是前两个指针,后一个是单步骤。前导指针处理的是分辨率,如果它跟随后指针有一个周期。
额外 作者 Tenderdude,

Topological Sort (From Wikipedia):

在图论中,拓扑排序或   指导的拓扑排序   无环图(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)
0
额外
是的,请引用来源
额外 作者 Jason S,
呃...直接从维基百科复制?
额外 作者 Benjol,
谢谢。帮助我映射可以使用此方法对依赖关系树进行排序的事实。 :-)
额外 作者 Shamasis Bhattacharya,

我希望这些需要的工具只需以深度优先的方式遍历树,当它们碰到树叶时,只需处理它(例如编译)并将其从图中移除(或将其标记为已处理,并将所有叶作为叶子处理)。

只要它是一个DAG,这个简单的基于栈的步行应该是微不足道的。

0
额外
是的,你就是这么做的。它被称为深度优先搜索(DFS)。除非你确定你有一个DAG,否则你必须检查后沿,否则一个周期会让你陷入无限循环。
额外 作者 sleske,