当前位置：文江博客话题详情

如何将无向图转换为 DAG？

发布于 2024-12-15 05:49:17 字数 358 浏览 3 评论 0原文

Wiki 页面说

任何无向图都可以通过为其顶点选择总顺序并将每条边从顺序中较早的端点定向到较晚的端点来制作为 DAG。

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

更多信息：我正在研究一个无向图，它有一个源和一个接收器。我试图引导这些边缘，以便通过遵循边缘方向，我可以从源头到达接收器。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

素衣风尘叹 2024-12-22 05:49:17

全序基本上只是按某种顺序排列所有顶点——可以将其视为用 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

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.

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.

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.

eg. if you had

  A
 / \
B---C

and you started by exploring A, you would orient edges incident on A away from A:

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

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

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.

Response to "More Info":

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

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

回复收藏 0 原文

在巴黎塔顶看东京樱花 2024-12-22 05:49:17

实际上我认为维基页面中“选择总订单”的含义是指您自己定义总订单。换句话说，如果我们检查最简单的无向图：

A----B

将这个无向图转换为 DAG 显然取决于你选择将 A 排序在 B 之前还是将 A 排序在 B 之后。如果你选择 A 在 B 之前，那么它就变成：

A--->B

否则，它就变成：

B--->A

这正是从“EARLIER”端点（在总顺序中出现较早的端点）到“LATER”端点“定向每条边”的含义。

类似地，对于：

    A
   / \
  /   \
 B-----C

如果将总顺序定义为：

B A C

那么有向图应该类似于：

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

Actually I think what it means in the wiki page by "choosing a total order" means defining a total order yourself. In other words, if we check the simplest undirected graph:

A----B

Converting this undirected graph to a DAG clearly depends on whether you choose to order A before B or A after B. If you choose A before B, then it becomes:

A--->B

Otherwise, it becomes:

B--->A

That is exactly what it means by "orienting every edge" from the "EARLIER" endpoint (endpoints that appear earlier in the total order) to the "LATER" endpoint.

Similarly, for:

    A
   / \
  /   \
 B-----C

If you define the total order as:

B A C

Then the directed graph should be something like:

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

回复收藏 0 原文

旧话新听 2024-12-22 05:49:17

问题是，在我们将无向边更改为有向边之后，我们不希望留下任何循环。

例如，假设我们有完整的三角形图，

A -- B
  \  |
   \ |
     C

我们可以选择边的方向为 A -> 。 B、B-> C和C->答：

A -> B
 \\  |
   \ v
     C

但是我们会得到一个循环，但它不是有向无环图。

维基百科页面中建议的技巧是选择顶点的顺序，实际上是任何顺序，并使用它来决定指向边缘的方向。

由于边在排序中指向上方，因此我们永远不会再次“回落”来完成一个循环，因此保证生成的图是非循环的。

The problem is that after we change our undirected edges into directed ones we don't want any cycles left.

For example, suppose we have the complete triangle graph

A -- B
  \  |
   \ |
     C

We could choose orientations for the edges as A -> B, B -> C and C -> A

A -> B
 \\  |
   \ v
     C

But then we'd get a cycle and that is not a Directed Acyclic Graph.

The trick suggested in the Wikipedia page is choose an ordering of the vertices, any ordering, actually, and use that to decide what directions to point the edges.

Since the edges point upwards in the ordering we can never "fall back down" again to complete a cycle so the resulting graph is guarantted to be acyclic.

回复收藏 0 原文