有序 DAG 遍历

Question

我有一个代表多个任意布尔表达式的 DAG。 DAG 由两种类型的节点组成：

1. 叶节点（由属性、运算符、值组成的谓词）
2. 中间节点（AND/OR）

图中的每个节点都可以在其他表达式中作为子表达式重用。

例如，要计算 OR/AND 节点，必须首先计算它的谓词（或中间节点）。

是否有任何优化算法可以为以谓词节点为起点的 DAG 提供这种自下而上的层序遍历？

Answer 1

您要找的是topological sort。让我为您编写带有解释的伪代码。这个想法是，如果存在从 u 到 v 的路径，那么 v 会出现在排序中的 u 之后。

在这两种实现中，我们将创建一个名为 output 的数据结构，并将顶点一一附加到其中。最终，output 会给我们 topological order.

第一次实施：

1. 计算所有顶点的度数。
   顶点的入度是与该顶点相邻的头端数。
2. 找到入度为0的顶点u，并将其存储在output中。如果没有这样的顶点，则说明图不是无环，因此没有拓扑序。
3. 从图中删除 u 及其所有边。
4. 必要时更新剩余顶点的入度。
5. 重复步骤 2,3 和 4 V 次，V 是图中的顶点数。
   此实现的时间复杂度为 O(V^2).

更高效的实施：

1. 计算所有顶点的入度。
2. 将入度为0的所有顶点存储在任意数据结构中* A并将所有入度为正的顶点存储在另一个任意数据结构中B。
3. 从 A 中删除顶点 u 并将其存储在 output 中。
4. 对于所有边 (u, v)，更新v的入度。如果 v 的入度为 0，则从 B 中取出并放入 A.
5. 重复步骤 3 和 4，直到 A 和 B 变为空。
   此实现的时间复杂度为 O(V + E)，E 是图中的边数。

*= 任何允许在 O(1)（常数时间）中添加和删除的数据结构都可以。

请注意 topological order 可能不是唯一的。例如，图表中的 attr_2>=200 和 attr_3 IN ["yellow", "green"] 节点之间没有层次结构。所以他们各自的顺序可能会有所不同。