代码之家 › 专栏 › 技术社区 › Coxy

简单依赖算法的问题

directed-acyclic-graphs dependencies tree sorting algorithm

22

Coxy · 技术社区 · 15 年前

在我的webapp中,我们有许多字段汇总了其他字段,而这些字段汇总了更多字段。我知道这是一个有向无环图。

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

例如: A=B+D,D=B+C,B=C+E 高效计算顺序:E->C->B->D->A

现在,我的算法只是迭代地将简单的插入到列表中,但我遇到了一些情况,这些情况会开始出现中断。我在想,相反,需要什么来将所有的依赖关系计算成一个树结构,并从那里转换成一维形式?有没有一个简单的算法将这样一棵树转换成一个有效的顺序?

2 回复 | 直到 15 年前

1

29

quark 15 年前

你在找吗 topological sort 是吗?这在DAG上强制排序(序列或列表)。例如,电子表格使用它来计算计算单元之间的依赖关系。

2

9

caf 15 年前

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

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

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

    AddToList(F)
}

然后依次对每个字段调用existeField(),然后根据您的规范以最佳顺序填充列表。

请注意,如果字段是循环(也就是说,你有类似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。