别说话写代码.
2019-07-11 13:06
采纳率: 50%
浏览 506

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

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


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



问题:



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

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



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


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

1条回答 默认 最新

相关推荐 更多相似问题