在 DAG 中合并不可达的顶点可能会产生循环？

Question

我有一个 DAG（有向无环图），其中我需要合并一些彼此不可达的顶点。我的最终图表应该是 DAG。我的问题是做这个操作，最后的图能有环吗？

Answer 1

如果你确实一次合并一对，在每一个之后重新检查可达性，那么，不，不可能引入一个循环，因为它必然涉及合并的顶点，这意味着它的弧会导出一条路径在原始图表中。

否则转换后的图有可能出现环路

A    B
|    |
|    |
v    v
B    A

合并 A。合并 Bs.