Han*_*etz 14 algorithm graph-theory
我有一个DAG存储我的应用程序中的某些对象之间的关系.当通过在现有顶点下面添加新顶点(即,隐式地在新顶点中创建新边)并且然后(在任何稍后时间)从那里到其他顶点的新边缘来更新此结构时,我想确保图形保持DAG,即我的代码不会创建周期.
我是否必须为每个插入和连接操作添加一个循环检测,或者是否有我可以遵循的规则,这将保证我不会产生循环？
我能想到的一种方法是存储每个节点的拓扑级别,并且只允许指向更高级别(远离源节点)的新边缘.然而,看起来这实际上会让我失去很多我希望通过使用DAG而不是一组普通树来实现的灵活性.
您还可以存储反向链接,并检查正在添加的边的终点节点是否未出现在原始节点的任何父节点中.这比进行全周期检测要快.本质上,这将是反向链路上的最短路径算法,对于DAG应该是线性操作.
作为@Markus说,不过,如果你没有创建两个链接到和来自新的节点到现有节点,你不应该能够通过引入新的节点,以图建立一个循环.
通过添加新顶点然后从那里添加新边到其他顶点来更新此结构
如果所有新边都来自新顶点,则不会创建周期.
如果您还要从旧节点向新顶点添加边,则选项取决于图的预期形状.它们都归结为部分排序的变化,但是有一些黑客能够为树木,森林,钻石网格等提供更好的性能.您对预期的整体图形形状了解多少？