匹配节点的图形算法
给定一个有向图，我可以使用什么算法来查找其边的随机子集，以便每个节点都有一个传入边和一个传出边？
例如，这可能是我给出的图表：
这将是一个有效的输出图表：
这是有效的，因为：
- 它包含输入图上的所有节点
- 它的所有边也在输入图上
- 每个节点恰好有一条离开它的边和一条到达它的边（并且不能是同一条边，不允许循环，每个节点必须连接到至少一个其他节点）。
如果没有可能的解决方案应该被检测到。
有没有有效的算法来解决这个问题？
谢谢！
Given a directed graph, what is an algorithm I can use to find a random subset of its edges so that every node has exactly one incoming and exactly one outgoing edge?
For example, this could be the graph I am given:
And this would be a valid output graph:
This is valid because:
- It contains all the nodes on the input graph
- All its edges are also on the input graph
- Every node has exactly one edge leaving it and one edge coming to it (and that can't be the same edge, no loops are allowed, every node has to connect to at least one other node).
If there is no possible solution that should be detected.
Is there an efficient algorithm to solve this?
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这是一个节点周期覆盖问题。它可以被解决为二分图中的最大匹配。
简而言之：
It's a node cycles coverage problem. It can be solved as Maximum matchings in bipartite graphs.
In short:
您正在尝试将图表分解为一组循环。
此链接将您引向用于在图表中查找循环的 Tarjan 算法。
之后，您将需要一些搜索策略（鉴于您的限制，某些周期的选择可能不会导致解决方案）。
You're trying to decompose a graph into a set of cycles.
This link points you to Tarjan's algorithm for finding cycles in a graph.
After that, you'll need some search strategy (some choices of cycles may not lead to a solution given your constraints).