algorithm - 查找覆盖两个节点之间所有边的路径

Question

我们希望您能帮助我们解决以下问题:

给出一个可能包含环的有向图。必须找到一组满足以下条件的路径:

在从节点 A 到节点 B 的途中可以通过的所有边都必须被集合内的路径覆盖(一条边可以是集合中多条路径的一部分)

解决方案不一定是路径数量最少的解决方案，路径也不一定是最短的。但是，该解决方案应该可以使用编程语言(如 java)有效地实现。我们需要生成一些测试用例的解决方案，覆盖节点 A 和节点 B 之间的所有边很重要。

大家都知道合适的算法吗？还是不存在有效的解决方案？

非常感谢您的建议! (我们已经在寻找解决方案，但我们找到的解决方案专注于最短路径并且效率极低)

这是我们问题的图形表示:

http://i.stack.imgur.com/wIY34.jpg

Answer 1

考虑从 A 可达的所有边 R(A)。可以通过在每条边上添加一个节点(即将每条边 U->V 变为 U->X->V)然后执行广度优先搜索来找到它们从 A 开始。

R(A) 之外的边显然不能在从 A 到 B 的路径上，因为那样它们就可以到达来自 A。所以到 B 的所有路径都必须经过 R(A) 的边。

因此我们要“覆盖”的边集 U 是 R(A) 的所有边，B 是可达的来自。

现在我们正在寻找一组从 A 到 B 的路径 S，其中包含 U 的所有边。

一个简单的方法如下:

• 将 R(A) 的所有边着色为黑色并设置 S={ }
• 虽然还有黑边:
  • 拍摄黑边 UV。
  • 如果 B 可以从 V 到达:
    • 构建路径P = A -> ... -> U -> V -> ... -> B
    • 将P的所有边都涂成灰色
    • 将P添加到S
  • 其他:
    • 将 UV 着色为灰色。
• 然后返回S

正如@user189 所指出的，如果我们考虑从 A 到 B 的可达边，我们允许路径两次通过 B。(即 a->b->c->g->f->e示例图像)。 他建议的解决方案(在计算 R(A) 之前删除节点 B)解决了这个问题。

关于复杂性:

R(A) 可以在 O(|E|) 时间内计算，并且从 A 到边 的路径R(A)中的UV可以直接从BFS树中读取。要检查从 V 到 B 的可达性并找到路径，我们可以使用 BFS 树从 B 开始并向后跟随边缘，在 O(| E|) 时间。

如果我们通过连接两个 BFS 树的边 UV 隐式引用路径，并使用 O(1) 读取/更新结构来维护黑色边集并在 BFS 树中查找边，我认为我们可以在 O(|E|) 时间内完成。