algorithm - 如何保证插入节点后 DAG 保持非循环状态？

Question

我有一个 DAG，用于存储我的应用程序中某些对象之间的关系。当通过在现有顶点下方添加新顶点来更新此结构时（即，在新顶点中隐式创建新边），然后（在以后的任何时间）从那里到其他顶点的新边，我想确保图保持 DAG，即我的代码不会创建循环。

我是否必须为每个插入和连接操作添加循环检测，或者是否有可以在插入时遵循的规则来保证我不会产生循环？

我能想到的一种方法是存储每个节点的拓扑级别，并且只允许指向更高级别（离源节点更远）的新边。但是，这似乎实际上会剥夺我通过使用 DAG 而不是一组普通树来实现的许多灵活性。

Answer 1

您还可以存储反向链接，并检查所添加边的终点节点是否未出现在源节点的任何父节点中。这将比进行全周期检测更快。本质上，这将是反向链路上的最短路径算法，对于 DAG 应该是线性操作。

但是，正如@Markus 所说，如果您没有创建新节点到现有节点的链接，那么您不应该通过向图中引入新节点来创建循环。

Answer 2

当通过添加新顶点和从那里到其他顶点的新边来更新此结构时

如果所有新边都来自新顶点，您将永远不会创建循环。

如果您还打算从旧节点向新顶点添加边，您的选项取决于图形的预期形状。它们都归结为偏序的变化，但是有一些技巧可以为树木、森林、菱形网格等提供更好的性能。您对预期的整体图形形状了解多少？

Answer 3

您可以做的是保持节点按拓扑排序（搜索“拓扑排序”）。当您添加从低阶节点到高阶节点的弧时，您知道没有创建循环。在相反的情况下，您需要增量更新拓扑排序并同时运行循环检测。