绘制算法以匹配节点

Question

鉴于有向图，我可以使用什么算法来找到其边缘的随机子集，以便每个节点都具有一个传入和一个传出的边缘？

例如，这可能是我得到的图：

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

这是有效的，因为：

• 它包含输入图上的所有节点
• 其所有边缘也都在输入图上
• 每个节点都有一个边缘，并且一个边缘即将到来（不可能是相同的边缘，不允许循环，每个节点都必须连接到至少一个其他节点）。

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

是否有有效的算法来解决此问题？

谢谢！

Answer 1

这是节点循环覆盖问题。可以解决 两分图中的最大匹配.

简而言之：

1. 将每个节点分为两个，每个节点一组为图，以便所有边缘从分区P1转到分区P2。在您的样本中，节点A和D将变成P2中的分区P1和A2，D2中的节点A1，D1。 Edge AD将变成A1-D2，然后将DA-变为D1-A2。
2. 然后找到最大匹配，存在一些算法。
3. 然后将节点返回，您将获得一个周期覆盖范围。

Answer 2

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

这个链接 将您指向Tarjan的算法，以在图中查找周期。

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