如何在不创建循环的情况下向有向无环图添加边

Question

我有一个包含有向边和无向边的图，现在我想通过用有向边替换它们来摆脱无向边（每个无向边都变成一个有向边）。每个无向边有两种可能（用一个方向或另一个方向的有向边替换它）。

如何确定无向边的方向以使我的图保持非循环？

我的做法：

创建一个仅包含有向边的图，稍后将无向边 1 乘 1（作为有向边）添加。现在我有一个 DAG，我的问题减少到在保持 DAG 属性的同时向图中添加有向边（只有有向边，没有循环）。

如何向 DAG 添加边并确保生成的图也是 DAG？

Answer 1

让我们通过一个例子来尝试解决这个问题：-

假设我有以下一组顶点作为定向顶点：-

(1,2)
(2,3)
(4,5)
(5,6)
(7,3)

并且我们跟随一组具有无向顶点的顶点：-

(3,4)
(6,7)

所以现在如果我们在纸上创建图表，它应该看起来像这样

1 -> 2 -> 3 
         /  \
        /  4   -> 5 -> 6
       /              /  \
     -----------------7

所以你可以清楚地看到存在两个无向边，我们想用有向边替换它们，

所以我们可以选择第一个无向对作为 (3,4) 并放置一个顶点 3 -> 4 然后我们将调用 dfs(1)，如果找到一个循环则 (3,4) 是不是有效的，然后我们将放置为 4 -> 3 但在我们的情况下 3 -> 4 不会导致任何循环。

我们继续我们的下一对称为 (6,7) 并放置 6 -> 7 导致一个循环，所以我们放置 7 -> 6 这给了我们一个 DAG。

这就像一个蛮力解决方案。让我再考虑一下，有没有更好的方法来解决这个问题。

Answer 2

使用您拥有的所有有向边构建初始 DAG。拓扑排序。将排序强加的偏序扩展为全序（例如，将顶点排列在层格中并逐层枚举）。请注意，所有边都从较小的顶点到较大的顶点。

现在根据总顺序（从较小的顶点到较大的顶点）定向您的无向边。很容易看出生成的图形没有循环（要存在循环，必须有一条沿相反方向的边）。

Answer 3

这对我有用：

对没有无向边的图进行拓扑排序，将无向边一条一条相加（使拓扑值从大到小）

这样保证DAG加边后还是DAG

@user58697，不需要扩展部分顺序，因为在对图进行拓扑排序后存在总顺序。每个节点的 topo-value 与其他 topo-values 具有可比性。

Answer 4

在不创建循环的情况下向 DAG 添加 link

它从不创建循环。

Answer 5

基本思路是做拓扑排序。

例如拓扑排序后数组为3,4,5,6,1,2 我们从 3 指向无向边 -> 其他边
之后做 4 次，然后 5 次，依此类推

这样保证DAG加边后还是DAG

Answer 6

完成！

How to add edges to a directed acyclic graph without creating cycles