简单依赖算法的问题

在我的webapp中，我们有许多领域总结其他领域，这些领域总结更多的领域。我知道这是一个有向无环图。简单依赖算法的问题

当页面加载时，我计算所有字段的值。我真正想要做的就是将我的DAG转换为一维列表，其中包含一个计算字段的有效顺序。

例如： A = B + D，D = B + C ，B = C + E 有效的计算顺序：E - > C - > B - > D - > A

现在我的算法只是简单地迭代插入List，但我遇到了一些情况开始中断。我在想什么需要改为将所有依赖项编译为树结构，然后将其转换为一维形式？有没有一种简单的算法将这种树转化为有效的排序？

来源

2009-07-28 Coxy

你是在找topological sort？这在DAG上施加了一个排序（一个序列或列表）。例如，它被电子表格用来计算单元之间的依赖关系以进行计算。

来源

2009-07-28 06:24:20 quark

非常感谢，这正是术语，我之后。 – Coxy 2009-07-28 08:03:30

你想要的是深度优先搜索。

function ExamineField(Field F) 
{ 
    if (F.already_in_list) 
     return 

    foreach C child of F 
    { 
     call ExamineField(C) 
    } 

    AddToList(F) 
}

然后，只需依次在每个字段上调用ExamineField（），并根据您的规范以最佳顺序填充列表。

请注意，如果字段是循环（也就是说，您有类似于A = B + C，B = A + D的东西），那么必须修改该算法以便它不会进入无限循环。

对于你的榜样，呼叫会去：

ExamineField(A) 
    ExamineField(B) 
    ExamineField(C) 
     AddToList(C) 
    ExamineField(E) 
     AddToList(E) 
    AddToList(B) 
    ExamineField(D) 
    ExamineField(B) 
     (already in list, nothing happens) 
    ExamineField(C) 
     (already in list, nothing happens) 
    AddToList(D) 
    AddToList(A) 
ExamineField(B) 
    (already in list, nothing happens) 
ExamineField(C) 
    (already in list, nothing happens) 
ExamineField(D) 
    (already in list, nothing happens) 
ExamineField(E) 
    (already in list, nothing happens)

，榜单最终将C，E，B，d，A

来源

2009-07-28 06:31:47 caf

非常感谢这个例子！这正是我想要做的，尽管我最终选择了迭代算法。 – Coxy 2009-07-28 08:04:06

简单依赖算法的问题

回答

相关问题