在有其他限制的情况下向有向无环图添加边

我有一个 DAG。我有这个操作来在两个节点之间添加一条边。

如果 A 可从 B 到达，则 B 是 A 的父级。如果 A 可以从 B 到达，而无需通过另一个节点，则 B 是 A 的直接父节点。

该图的要求是：

1. 没有循环。
2. 对于任何节点，都有一个直接父节点列表 P[1],P[2],P[3]... 对于任何 i 和 j，P[i] 都不是 P[j] 的父节点。

如果添加一条边，则不满足要求1，则不构造该边。 如果添加一条边，则不满足要求 2，则构造该边，但将以满足要求 2 的方式修改直接父级。

例如有3个节点

• A、直系父母：无
• B、直系父母：A
• C、直系父母：A

现在，如果我在 B 和 C 之间添加一条边，我们有

• C、直系父母：A、B

但 A 是 B 的父代，不满足要求 2，因此 A 从 C 的直接父代中删除，我们有

• C、直系父母：B

目前这是我所做的： 添加从 A 到 B 的边（此 A 成为 B 的父级）

1. 通过 BFS 检查 B 是否是 A 的父级。如果是这样，请不要添加边缘。（这确保没有循环）
2. 通过 BFS 检查 A 是否已经是 B 的父级。如果是这样，请勿添加边缘。
3. 找到 A 的父级与 B 的直接父级的交集。这是通过 BFS 找到 A 的每个父级来完成的。删除 B 的直接父级的交集，并将 A 添加为 B 的直接父级。（2 和 3 确保它满足要求 2）

这很慢。它在 5k 节点级别崩溃（我正在寻找它来处理任何少于 100k 节点的图），速度变得不可接受，添加节点边缘需要 0.02 秒。

我有一种感觉，第 1 步和第 2 步可以使用其他算法一步完成。

我想过使用拓扑排序，但它必须横贯整个图，这是我的步骤 1 和 2 中最糟糕的情况。当添加新节点时，顺序将被打乱。所以我每次插入时都必须运行拓扑排序，因此它不会产生任何好处。 对于第 3 步，必须找到 A 的整个父母集。这个过程相当缓慢，因为平均来说它横穿了图表的相当一部分。

我怎样才能使这个更有效率？

您的问题归结为“在 DAG 中插入边能否比 O(v+e) 更快完成？”按要求（1）。要求 (2) 是一个更局部的约束，不需要检查整个图。

我认为答案是否定的：你不能做得更好O(v+e)在最坏的情况下（其中v是节点/顶点的数量，e是边数）。

毫无疑问，有一些技巧可以提高预期性能，具体取决于 DAG 的属性及其随时间的变化情况。这似乎是一个活跃的研究课题。例如，我想对于某些图来说，它可能对集群节点有益。然后，在集群内插入边只需要在集群子 DAG 内进行检查。但是，您需要一个适当的集群策略，并支持在添加节点等时以廉价的方式更新集群。