(回溯法)求无向图的所有哈密顿回路 您所在的位置:网站首页 回溯法求解哈密顿回路问题例题 (回溯法)求无向图的所有哈密顿回路

(回溯法)求无向图的所有哈密顿回路

2024-07-12 11:24| 来源: 网络整理| 查看: 265

给定一个无向图,由指定的起点前往指定的终点,用回溯法来进行解题时,最好的方法就是用递归算法,可以清晰明了的设置好每一步,由于哈密顿回路是所有顶点都需要经过且只能经过一次,所以需要设置一个解向量数组x[ ]来记录已经经过的顶点;那在判断每个边,经过每个点时,需要将可能从起点到达终点的路径都要记录下来,我们选择使用vector容器来记录每一个经过的路径。

vector path

跟蛮力法有些相似,核心思想就是把当前访问的顶点所连接的所有顶点都用递归法访问一边,直到找到的最后一个顶点恰好为终点时,将路径进行输出。

void Ham(int i,int num,int x[],vector path){ if(num==1&&s[i][End]) //只剩最后一个点且刚好为终点 {path.push_back(End); display(path); return;} else if(num==1) return; //减枝 else if(num>1){ for(int j=1;j{0,0,0,0,0,0}, {0,0,1,1,0,1}, {0,1,0,0,1,1}, {0,1,0,0,1,0}, {0,0,1,1,0,1}, {0,1,1,0,1,0}}; int First; int End; void display(vector path) { for(auto p=path.begin();p!=path.end();p++) { if(p!=path.begin()) cout


【本文地址】

公司简介

联系我们

今日新闻

    推荐新闻

    专题文章
      CopyRight 2018-2019 实验室设备网 版权所有