algorithm - 合并两个 DAG 的高效算法

Question

我有两个加权 DAG(有向无环图)，需要将它们合并为一个，这样我就可以获得拓扑排序(在某些情况下可能不止两个)。问题是每个图都是非循环的，但可以一起形成一个循环。此外，图很大(100k+ 节点，500k+ 边)。 有没有一种巧妙的方法来合并图表？同样好的是“一次”遍历所有图的算法。

编辑:

我所说的“合并”是指将两个图的所有边和顶点组合在一起(当然保留权重)，如果它们不创建循环的话。如果边缘已经存在，我想为其使用更大的权重。

这个想法是，从两个非循环图开始应该比简单地“修复”之后的结果更有优势(这意味着找到 NP 难的反馈弧集，所以我想避免这种情况)。

感谢您的建议。

Answer 1

一个问题是可能有不止一种解决方案。

例如考虑 DAGs {(a,b),(a,c)} 和 {(b,a),(b,c)}。您可以通过两种不同的方式“合并”它们:

1. {(a,b),(a,c),(b,c)}
2. {(a,c),(b,a),(b,c)}

解决方案的数量随着两个图的并集循环数的组合而增长，因此对于您的大图，您可能有大量的方法可以“合并”它们。

您是否有一个标准可以帮助您确定哪个 DAG 比另一个“更好”？