如何将一个无向的、非常循环的图转换为有向无环图？

Question

我正在研究修改过的TopSort算法，但是在寻找/创建用于测试的大型（超过1000个节点）有向无环图方面遇到了麻烦。我有一个来自另一个项目的无向样本图，大小适中，但有很多循环。是否有一种算法可以将边定向，以便不再存在循环？

- Frank D.

Answer 1

this 提供了获取无环图的方法。基本上，图遍历会产生一棵树，这棵树定义了原始节点的部分顺序。然后，只需将所有边定向，使它们要么指向部分顺序一致的方向，要么位于两个未排序的元素之间（这些可以指向任何方向）。

- lijie

---

我没有完全阅读，但据我理解：本文的第2.1节描述了将有向图转换为DAG（即打破循环）的方法。您建议添加一个先前步骤，使用（任何）遍历图形将无向图转换为有向图。 - Juh_

Answer 2

为了确保新的有向图是连通的，我会使用以下广度优先搜索。

 old_undirected graph G
 new_directed graph D
 dequeue Q
 v is any node in G
 add v to D
 Q.push_back(v)
 while(Q is not empty):
     v = Q.pop_front()
     for all neighbors u to v:
         if u in D
              add edge u->v to D
         else
              add u to D and add edge v->u to D
              Q.push_back(u)

 return D

这个图应该包含原始图的所有边，但是它们应该被定向，以便不会出现任何环。

- Bertil Baron

Answer 3

您想将图形转换为根树森林。对于图形的每个连通分量进行广度优先或深度优先遍历。在遍历期间，在父子顶点之间建立有向边。

参见http://en.wikipedia.org/wiki/Graph_traversal。

- gdj

---

嗯，他不是想制作树。他想指定每条边，以便生成的图形是无环的。而且所提出的方法将删除一些边（从而形成一棵树）。 - lijie