Tho*_*mas 11 algorithm graph directed-acyclic-graphs
我有两个加权DAG(有向非循环图)并需要将它们合并为一个,所以我可以得到一个拓扑排序(在某些情况下它可能超过两个).问题是图表各自都是非循环的,但可以一起形成一个循环.此外,图形很大(100k +节点,500k +边缘).有没有一种聪明的方法来合并图表？同样好的将是一次"一次"遍历所有图形的算法.
编辑:
通过"合并",我的意思是将两个图形的所有边和顶点组合在一起(当然保留权重),如果它们不创建周期的话.如果边缘已经存在,我想为它使用更大的权重.
这个想法是从两个非循环图开始应该比以后简单地"修复"结果更有优势(这意味着找到NP难以反馈的弧集,所以我想避免这种情况).
谢谢你的建议.
假设两个图的顶点相同，如果不是，只需考虑
V = V1 U V1
假设您有一个邻接列表。现在，对于 V1 和 V2 中的每个顶点 v，您可以按边通向的顶点对邻接列表进行排序（如果是（顶点，权重）对，则按顶点排序）。由于图形很小，这不应该那么昂贵，而且应该summation degree(v)*log(degree(v))不会那么糟糕。
之后，您可以迭代 V1 和 V2 中的所有顶点 v，并对 V1 和 V2 中 v 的邻接表进行合并排序。这类似于使用合并排序查找 2 个排序数组的并集，只是当您发现两个数组中都出现一个元素时，您可以选择较大的边。