java - 向无环图添加边

Question

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

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

我的方法:

对没有无向边的图进行拓扑排序，将无向边一条一条相加(使它们从较小的拓扑值指向较大的拓扑值)。

这似乎不起作用，因为拓扑排序创建了部分顺序(并非所有顶点都可以相互比较)，我需要的是一个总顺序(所有顶点都可以比较)。如何将偏序扩展为全序？

我的方法失败的示例图:

• n = 8(顶点数，从1到n编号)
• m = 5(有向边数)
• l = 6(无向边数)

有向边:

1. 2 -> 1
2. 3 -> 2
3. 2 -> 6
4. 4 -> 5
5. 5 -> 8

无向边:

1. 1 <-> 4
2. 2 <-> 5
3. 3 <-> 7
4. 4 <-> 8
5. 6 <-> 7
6. 6 <-> 8

只有有向边和顶点旁边的拓扑序值的图:

现在，当我开始添加无向边(并根据拓扑顺序值引导它们)时，我在添加边 8 -> 4 后得到一个循环:

https://en.wikipedia.org/wiki/Directed_acyclic_graph

Answer 1

根据定义，拓扑排序是一个线性顺序，每个线性顺序都是一个总顺序，所以理论上，您的方法很好。但是，您的实现是错误的。

即在您的拓扑顺序定义中，如果存在从 a 到 b 的边，则 b < a。但是在你的第二张图中，你打破了规则并添加了一条从 4 到 6 的边(6 > 4!)，你混合了顶点的标识符(8 和 4)及其拓扑顺序(4 和 6)。