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 吗？如果是这样，我将如何进行？
更多信息:我正在处理一个具有一个源和一个汇的无向图。我正在尝试引导这些边缘，以便通过沿着边缘方向我可以从源头到达汇点。
最佳答案
总序基本上只是按某种顺序排列所有顶点——可以将其视为用从 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
关于algorithm - 如何将无向图转换为 DAG？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8127932/