我有两个加权DAG(有向非循环图)并需要将它们合并为一个,所以我可以得到一个拓扑排序(在某些情况下它可能超过两个).问题是图表各自都是非循环的,但可以一起形成一个循环.此外,图形很大(100k +节点,500k +边缘).有没有一种聪明的方法来合并图表？同样好的将是一次"一次"遍历所有图形的算法.
编辑:
通过"合并",我的意思是将两个图形的所有边和顶点组合在一起(当然保留权重),如果它们不创建周期的话.如果边缘已经存在,我想为它使用更大的权重.
这个想法是从两个非循环图开始应该比以后简单地"修复"结果更有优势(这意味着找到NP难以反馈的弧集,所以我想避免这种情况).
谢谢你的建议.