algorithm - 如何将无向图转换为没有循环的有向图(Directed acyclic graph)

Question

我有一个无向图，我希望将其转换为有向图。我将很少有约束，例如已经有一些定向关系。

Answer 1

您实际上是在尝试构建一个 DAG从您的基础架构图中。请注意，有向图是 DAG 当且仅当它可以是 topologically sorted。 .

那么，让我们从头到尾。首先创建拓扑排序，然后按照排序的方式连接节点。

• 首先，删除所有“未确定”的边，只保留那些您已经知道方向的边。
• 然后，对图进行拓扑排序，找到某种拓扑排序(如果没有，则在给定的限制条件下问题无法解决)。
• 以此为基础，从first到last设置每条边的方向，使得源节点为拓扑排序较低的节点。

算法的时间复杂度与节点数和边数成线性关系。