jos*_*eph 4 algorithm graph-theory graph cycle
我已经指示了很多周期的图形,可能是强连接的,我需要从它获得一个最小的周期.我的意思是我需要得到循环,这是图中最短的循环,并且每个边缘至少被覆盖一次.
我一直在寻找一些算法或一些理论背景,但我发现的只有中国邮递员算法.但是这个解决方案不适用于有向图.
有谁能够帮我？谢谢
编辑>>该图的所有边具有相同的成本 - 例如1
看看这篇论文 - " 定向中国邮递员问题".这是正确的问题分类(假设没有更多的限制).
如果您只是阅读理论,请仔细阅读此页面,该页面来自算法设计手册.
关键引用(定向版的下半部分):
可以通过向图G添加适当的边来构造最佳的邮差旅行,以使其成为欧拉.具体来说,我们在G中找到每对奇数顶点之间的最短路径.在G中的两个奇度顶点之间添加一条路径,使它们都变为偶数度,从而使我们更接近欧拉图.找到要添加到G的最佳最短路径集,可以减少识别奇度顶点图中的最小权重完美匹配,其中边(i,j)的权重是从i到最短路径的长度.学家 对于有向图,这可以使用二分匹配来解决,其中顶点被分区,这取决于它们是否具有更多的进入边缘或外出边缘.一旦图形是欧拉,就可以使用上述过程在线性时间内提取实际周期.