简单依赖关系算法的问题
简单依赖关系算法的问题
提问于 2009-07-28 06:20:04
在我的webapp中，我们有许多字段汇总了其他字段，这些字段汇总了更多字段。我知道这是一个有向无环图。
当页面加载时，我计算所有字段的值。我真正想做的是将我的DAG转换成一个一维列表，该列表将包含一个有效的顺序来计算字段。
例如:A=B+ D，D=B+ C，B=C+E有效计算顺序:E -> C -> B -> D -> A
现在，我的算法只是迭代地对列表进行简单的插入，但我遇到了一些开始崩溃的情况。我在想，我们需要做的是把所有的依赖关系转换成一个树形结构，然后把它转换成一维的形式。有没有一种简单的算法可以将这样的树转换成有效的排序？
回答 2
Stack Overflow用户
回答已采纳
发布于 2009-07-28 06:24:21
你在找topological sort吗？这会对DAG施加排序(序列或列表)。例如，电子表格使用它来计算单元格之间的依赖关系，以进行计算。
Stack Overflow用户
发布于 2009-07-28 06:31:48
你想要的是深度优先搜索。
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结尾。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/1192200
复制相关文章
相似问题
腾讯云开发者
