weixin_41900122
爱编程的早起虫
采纳率100%
2019-07-11 13:06

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

40

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


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



问题:



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

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



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


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

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

1条回答

  • caozhy 回答这么多问题就耍赖把我的积分一笔勾销了 2年前

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

    点赞 评论 复制链接分享