我有一个有很多环的有向图，可能是强连通的，并且我需要从中得到一个最小的环。我的意思是，我需要获取在图中最短的环，每条边至少被覆盖一次。
我一直在寻找某种算法或理论背景，但我找到的唯一一件事是中国邮递员算法。但这个解决方案不适用于有向图。
有人可以帮助我吗？谢谢。
编辑>>该图的所有边都具有相同的成本 - 例如1
我一直在寻找某种算法或理论背景，但我找到的唯一一件事是中国邮递员算法。但这个解决方案不适用于有向图。
有人可以帮助我吗？谢谢。
编辑>>该图的所有边都具有相同的成本 - 例如1
最小路径 - 所有边至少经过一次
6
- joseph
2
我首先想到的是欧拉回路，但只是为了核实：每条边至少一次，还是恰好一次？ - ephemient
这不是作业，我需要至少一次机会，因为我不能保证我将在具有欧拉回路的图上运用它。 - joseph
5个回答
6
请看这篇论文 - 有向中国邮递员问题。虽然假设没有更多的限制，但这是正确的问题分类。
如果您只是阅读理论，请仔细阅读此页面，该页面来自算法设计手册。
关键引用（针对有向版本的后半部分）：
最优邮递员旅游路线可以通过向图G添加适当的边来使其欧拉化而构建。具体而言，我们在G中找到每对奇度顶点之间的最短路径。在G中添加两个奇度顶点之间的路径将它们都转换为偶数度，从而使我们更接近欧拉图。找到要添加到G中的最佳最短路径集合可归结为在奇度顶点上识别最小权重完美匹配，其中边（i，j）的权重是从i到j的最短路径的长度。对于有向图，这可以使用二分图匹配来解决，其中顶点根据它们是否具有更多的入射或出射边进行分区。一旦图形是欧拉图，就可以使用上面描述的过程在线性时间内提取实际循环。
如果您只是阅读理论，请仔细阅读此页面，该页面来自算法设计手册。
关键引用（针对有向版本的后半部分）：
最优邮递员旅游路线可以通过向图G添加适当的边来使其欧拉化而构建。具体而言，我们在G中找到每对奇度顶点之间的最短路径。在G中添加两个奇度顶点之间的路径将它们都转换为偶数度，从而使我们更接近欧拉图。找到要添加到G中的最佳最短路径集合可归结为在奇度顶点上识别最小权重完美匹配，其中边（i，j）的权重是从i到j的最短路径的长度。对于有向图，这可以使用二分图匹配来解决，其中顶点根据它们是否具有更多的入射或出射边进行分区。一旦图形是欧拉图，就可以使用上面描述的过程在线性时间内提取实际循环。
- Larry
0
我觉得这不是最优解，但如果图保证有一个环的话，你可以使用基于队列的搜索。每个队列条目都包含表示路径的节点列表。当你从队列中取出一个元素时，将所有可能的下一步添加到队列中，确保不会重新访问节点。如果最后一个节点与第一个节点相同，则找到了最小循环。
- recursive
0
我认为简单地写出哪些顶点是奇数，然后找到哪些组合会导致额外时间最少可能是值得的（如果权重是时间或距离），那么总长度将是每个边的权重加上额外的部分。例如，如果奇数顺序的顶点是A、B、C、D，则尝试AB&CD，然后是AC&BD等等。（我不确定这是否是一种特定命名的方法，但它对我有效）。 编辑：刚意识到这主要只适用于无向图。
- O.P
1
-1
当网络完全由有向边组成时，可以在多项式时间内解决特殊情况。我认为原始论文是匹配、欧拉游览和中国邮递员问题（1973） - 有关有向图问题的算法的清晰描述始于第115页（pdf文件的第28页）：
当一个连通图的所有边都是有向的且图形对称时，有一种特别简单和有吸引力的算法来指定欧拉游览...
在有向、对称、连通图G中找到欧拉游览的算法是首先找到G的生成树。然后，在任何节点n（除了生成树的根r），指定从n指向的边的任何顺序，只要生成树的边是排序中的最后一条即可。对于根r，指定任何顺序的边都可以。
范·阿登恩-埃伦费斯特和德布鲁因使用这个算法枚举了某个有向图中的所有欧拉游览[1]。
- ire_and_curses
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接