一个简单的依赖算法存在问题

Question

在我的web应用中，我们有许多字段汇总其他字段，并且这些字段又汇总更多的字段。我知道这是一个有向无环图。

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

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

目前，我的算法只是通过简单地向列表中迭代插入来进行操作，但我遇到了一些开始出现问题的情况。我在考虑是否需要将所有依赖关系都解析为树形结构，并从那里将其转换为一维形式？有没有一个简单的算法可以将这样的树转换为高效的排序？

- Coxy

Answer 1

你是否正在寻找拓扑排序？这种排序对有向无环图（DAG）进行排序，得到一种序列或列表。例如，在电子表格中，拓扑排序可用于计算单元格之间的依赖关系。请点击链接查看更多信息。

- quark

---

非常感谢，这正是我需要的术语。 - Coxy

Answer 2

您需要的是深度优先搜索算法。

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。

- caf

---

非常感谢您的示例！那正是我想做的，尽管最终我选择了迭代算法。 - Coxy