数学吧 关注:841,580贴子:8,571,817
  • 5回复贴,共1

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

只看楼主收藏回复

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

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


IP属地:宁夏1楼2021-03-17 22:36回复
    我不懂什么深度,回溯法
    但是我觉得可以用函数递归解决
    每走一步都调用一次函数本身
    走完后返回已走的路线
    直到走完


    IP属地:上海2楼2021-03-17 22:42
    回复
      定义一个函数
      前进(已走路线)
      循环
      下一步的分支
      更新已走路线
      前进(已走路线)
      循环结束
      函数结束


      IP属地:上海3楼2021-03-17 22:45
      收起回复