java - 匹配节点的图形算法

Question

给定一个有向图，我可以使用什么算法来找到它的边的一个随机子集，以便每个节点都有一个输入边和一个输出边？

例如，这可能是给我的图表：

这将是一个有效的输出图：

这是有效的，因为：

• 它包含输入图上的所有节点
• 它的所有边也在输入图上
• 每个节点都有一条边离开它，一条边到达它（不能是同一条边，不允许循环，每个节点都必须连接到至少一个其他节点）。

如果没有应该检测的可能解决方案。

有没有有效的算法来解决这个问题？

谢谢！

Answer 1

这是一个节点周期覆盖问题。它可以解决为二分图中的最大匹配。

简而言之：

1. 将每个节点一分为二，每个节点在图的一个分区中，以便所有边从分区 P1 到分区 P2。在您的示例中，节点 A 和 D 将变成分区 P1 中的节点 A1、D1 和 P2 中的 A2、D2。Edge AD 将变为 A1-D2，DA - 变为 D1-A2。
2. 然后找到一个最大匹配，一些算法存在。
3. 然后将节点合并回来，你就得到了一个循环覆盖。

Answer 2

您正在尝试将图形分解为一组循环。

此链接将您指向 Tarjan 的用于在图中查找循环的算法。

之后，您将需要一些搜索策略（考虑到您的限制，某些循环选择可能不会导致解决方案）。