algorithm - 编写将无向图更改为有向图的算法

Question

我需要帮助来解决这个问题:

你有无向图 G=(V,E) 你想写一个算法来调整所有其中一条边，使得在获得的有向图中，进入该节点的边数总是大于零。对于所有边 {u,v} ∈ E，您应该选择一个方向 (u,v) 或 (v,u)。当答案是肯定的时，算法必须返回边缘的意图——这满足了要求

Answer 1

正如所指出的，这个问题显然并不总是有解决方案。由于每个顶点必须至少有一个入边，如果我们有 E < V，则该问题是不可能的。

因此，假设我们有 E >= V。这是实现该算法的一种方法:首先，在 O(E) 时间内计算连接到每个顶点的边数。请注意，我的解决方案假定适当的存储，如邻接列表。你能看出为什么邻接矩阵的复杂性会更差吗？

其次，我们将根据顶点对应的边数在 O(V) 中生成顶点的二进制最小堆。一些直觉:如果我们有一个只有一条边的顶点，我们必须将其转换为一条传入边!当我们分配该边的方向时，我们需要更新另一侧顶点的边数。如果另一个顶点从 2 条边变为 1 条边，我们现在被迫将其一条边的方向分配给左侧。视觉上:

1 - 2 - 1

任意选择一条边数为1的有向

1 - 2 -> 0

2 刚刚失去了优势，所以更新为 1!

1 - 1 -> 0

由于它现在只有1条边，所以把它的边转换成incoming!

0 -> 0 -> 0

很明显，由于 V > E，此图不起作用，但您明白了。

所以，V 次，我们从堆中提取最小值并固定在 O(logV) 中。每次，减少邻居的边数。假设邻接表，我们可以找到一个邻居(第一个元素)并在 O(1) 中更新计数，我们可以在 O(logV) 中再次修复堆。总的来说，这一步需要 O(V logV)。

请注意，如果我们所有剩余的顶点都有不止一条可能的边，则此方法将任意选择边数最少的顶点之一，并任意选择其边之一。我会让你思考为什么这行得通(或者如果你认为行不通，请尝试提供一个反例!)最后，如果 E > V，那么当我们完成时，可能会留下额外的不必要的边缘。在 O(E) 时间内，我们可以任意为这些边分配方向。

总的来说，我们正在研究 V + V*logV + E aka O(E + VlogV)。希望这对您有所帮助!