如何将无向图转换为DAG？

Question

通过选择其顶点的总顺序并将每个边缘从顺序中的较早端点定向到后一个端点,可以将任何无向图形制成DAG.

但我不知道如何获得无向图的总顺序.我应该使用DFS吗？如果是这样,我将如何进行？

更多信息:我正在研究一个有一个源和一个接收器的无向图.我试图引导这些边缘,以便沿着边缘方向我可以从源头到达接收器.

Answer 1

总顺序基本上只是按照某种顺序排列所有顶点 - 将其视为用1到| V(G)|的数字标记每个顶点.这为我们提供了一种一致的方法来了解我们检查的任何顶点对哪个顶点更高.

是的,您可以通过深度优先搜索获得总排序.每次在DFS中探索顶点时,只需为每个顶点指定递增计数器的值.这是您如何获得总订购.

但是,您无需明确获取总排序的标签即可获得DAG.如果我们使用上述探索时间作为我们的排序,那么我们可以按如下方式进行:在进行DFS遍历时定向边缘,将每个无向边缘指向远离当前正在扩展的顶点.

基本上,我们之前探索过的顶点指向稍后探索的顶点.

例如.如果你有

  A
 / \
B---C

而你从探索A开始,你会将边缘事件定位在远离A的A上:

A --> B
A --> C
B --- C

现在说你在DFS遍历中选择B来探索下一个.然后你将只留下A和B之间的边缘,因为你已经定位了这个边缘(A已经完全展开).B和C之间的边缘是未触及的,因此将其定位在远离当前顶点B的位置,以获得:

A --> B
A --> C
B --> C

当你探索C时,它的所有邻居都已完全展开,所以C没有什么可做的,并且没有更多的顶点需要探索.

回应"更多信息":

在这种情况下,只需确保首先展开源顶点,然后不要探索接收器.例如.对于

A-B-C
|/
D

其中D是源,B是接收器,你可以:展开D,然后是A,然后是C.你会得到:

D --> A
D --> B
A --> B
C --> B