如何将无向图转换为DAG？ [英] How to convert an undirected graph to a DAG?
问题描述
任何无向图都可以通过选择其顶点的总顺序并将每个边缘从顺序中较早的端点定向到较晚的端点而制成DAG。
Any undirected graph may be made into a DAG by choosing a total order for its vertices and orienting every edge from the earlier endpoint in the order to the later endpoint.
但是我不知道如何获得无向图的总阶。我应该使用DFS吗？如果是这样，我将如何进行？
But I don't know how to get the total order of an undirected graph. Should I use DFS? If so, how would I proceed?
更多信息：我正在处理一个有向源和一个汇的无向图。我正在尝试引导这些边缘，以便按照边缘方向从源到接收器。
More info: I'm working on an un-directed graph which has one source and one sink. I'm trying to direct these edges so that by following the edge direction I can get from the source to the sink.
推荐答案
总的顺序基本上只是将所有顶点按某种顺序排列-将其视为用1到| V（G）|的数字标记每个顶点。这为我们提供了一种一致的方式来知道我们检查的任何一对顶点中哪个顶点更高。
A total order is basically just arranging all the vertices in some order -- think of it as labelling each vertex with a number from 1 to |V(G)|. This gives us a consistent way to know which vertex is higher for any pair of vertices we examine.
是的，您可以使用深度优先搜索获得总排序。每次在DFS中浏览一个顶点时，只需为每个顶点分配一个递增计数器的值即可。这样便可以获取总订单。
Yes, you can obtain a total ordering with depth-first search. Just assign each vertex the value of an incrementing counter each time you explore a vertex in DFS. This is how you can get a total ordering.
但是您无需明确获得总订单的标签即可获得DAG。如果我们使用上述探索时间作为排序，则可以按以下步骤进行操作：在进行DFS遍历时将边定向，使每个无方向的边指向当前正在扩展的顶点。
But you don't need to explicitly get a labelling of a total ordering to get a DAG. If we use the above time-of-exploration as our ordering, then we can proceed as follows: Orient edges as you do the DFS traversal, pointing each undirected edge away from the vertex that you're currently expanding.
基本上，我们有较早探索的顶点，指向后来有探索的顶点。
Basically, we have vertices explored earlier pointing to vertices explored later.
例如。
A
/ \
B---C
然后您开始探索A，您将使A上发生的边缘偏离A：
and you started by exploring A, you would orient edges incident on A away from A:
A --> B
A --> C
B --- C
现在说您选择B来探索DFS中的下一个遍历。然后，您将不理会A和B之间的边缘，因为您已经确定了该边缘的方向（A已经完全展开）。 B和C之间的边缘未受影响，因此将其定位为远离我们当前的顶点B，以得到：
Now say you choose B to explore next in your DFS traversal. Then you would leave the edge between A and B alone, because you've already oriented that edge (A has already been fully expanded). The edge between B and C was untouched, so orient that away from our current vertex, B, to get:
A --> B
A --> C
B --> C
当您探索C时，它的所有邻居都已完全展开，因此没有任何余地为C做，没有更多的顶点可以探索。
When you explore C, all of its neighbours have been fully expanded, so there is nothing left to do for C, and there are no more vertices left to explore.
响应更多信息：
在这种情况下，只需确保首先扩展源顶点即可，而不必探索接收器。例如。
In that case, just make sure you expand the source vertex first and just don't explore the sink. Eg. for
A-B-C
|/
D
其中D是源，B是宿，您可以：依次扩展D，A，C。
where D is the source and B is the sink, you could: expand D, then A, then C. You would get:
D --> A
D --> B
A --> B
C --> B
这篇关于如何将无向图转换为DAG？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
