数学吧 关注:844,988贴子:8,585,994
  • 0回复贴,共1

诸位朋友,想写一个关于图的程序,遇到一个问题,求解

取消只看楼主收藏回复

问题描述:如有描述不规范的请指出,尽力了
存在一个连通图,不确定是否存在哈密顿通路,如何找到一条路径如V1--V2--…--Vn,使其经过尽可能多的顶点且每个顶点只能经过一次?
可能等同于的描述:
如何寻找一个连通图中的最大初级通路?
想法:使用深度优先(回溯法)的算法尽可能遍历更多的顶点,但什么条件能帮助程序的判断结束?

也就是说,如上图,
经过两遍搜索,得到了2条路径 : 0—1—3—4—5—6
0—1—2—5—6
已经获得了优质的结果,这时候想结束程序,什么能作为结束的判断条件......?


IP属地:宁夏1楼2021-03-17 22:36回复