代码之家 › 专栏 › 技术社区 › Chao Xu

添加边到具有其他限制的直接非循环图

directed-acyclic-graphs graph-theory

4

Chao Xu · 技术社区 · 17 年前

此图表的要求如下:

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

例如,有3个节点

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

但A是B的父级,不满足要求2,因此A从C的直接父级中移除,我们有

现在我做的是:

通过BFS检查A是否已经是B的父级。如果是,请不要添加边。
找到A的父对象与B的直接父对象的交点。这是通过查找一个虽然BFS的每个父级来完成的。从B的直接父对象中删除交点,并添加A作为B的直接父对象。(2和3确保其满足要求2)

这太慢了。它在5k节点级别发生故障(我正在寻找这个来处理任何少于100k节点的图形),速度变得不可接受,添加节点边缘需要0.02秒。

我有一种感觉,第一步和第二步可以用其他算法在第一步中完成。

我曾想过使用拓扑排序,但它必须横穿整个图,这是我的步骤1&2.添加新节点时,排序将中断。所以每次插入时我都要运行拓扑排序,所以不会产生任何好处。

我怎样才能提高效率?

2 回复 | 直到 13 年前

1

4

Wim Coenen 17 年前

根据要求(1),您的问题归结为“在DAG中插入边是否可以比O(v+e)更快?”。需求(2)是一个更局部的约束,不需要检查整个图。

我认为答案是否定的:你不能比我做得更好 O(v+e) 在最坏的情况下(在哪里 v 是节点/顶点的数量,以及 e 是边数)。

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

2

0

Dewfy 17 年前

每行索引必须存储对metaparent元child

metaparent-链接中的父级:父级,父级的父级,。。。

metachid-链接中的子对象:子对象,子对象的子对象。。。

对于图A->B->C存在以下索引: A-B,B-C,A-C