欧拉回路避桥法的扩展:遍历无向图里的所有边,当这个图不是欧拉回路时,怎样使得走过的重复边最少?

遍历所有点的问题是tsp问题,但是如果需要遍历所有的边呢?


欧拉回路的避桥法可以对于欧拉回路,实现不重复的遍历所有边,
但是如果该图不是欧拉回路,该怎样在最短行驶路径下遍历所有边呢?



问题:



给定一个无向连通图,不是欧拉图,需要遍历其中所有**边**,

可以重复走边,问:怎样使得走过的重复路径最少?



做课设需要解决这个问题,有相关的算法吗,


如果没有,该怎样修改对于欧拉回路的避桥法呢?

1个回答

这个叫做 中国邮递员问题,你可以google下
https://www.cnblogs.com/WABoss/p/5140531.html

weixin_41900122
爱编程的早起虫 多谢,请问有python实现的代码吗?
9 个月之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问