汉密尔顿回路问题

概述

这是自己这学期算法课的实验作业。下面给出汉密尔顿图的定义。定义如下：对于连通图G=（V，E），V1，V2，…，Vn是G 的一条通路，且图中任意两个顶点都可达，若 中每个顶点在该通路中出现且仅出现一次，则称该通路为汉密尔顿通路。若 V1=Vn，则称该通路为汉密尔顿回路。

---

算法描述

1）初始化最佳路径数组best_path，同时初始化临时路径数组path与访问数组isvisited，设置最小长度min，设置长度变量length = 0
2）开始对每个顶点进行遍历寻找最佳路径，首先堆访问数组中对应顶点进行置1，并把当前顶点追加到path，同时利用cur_vertex这个临时变量保存当前结点，并开始进行循环。
3）找到出cur_vertex之外与之相邻且并未访问的一个顶点k，利用tmp保存这两点之间的权重，之后检查是否存在比tmp更小且与cur_vertex相邻的顶点，如有则更新tmp与访问的顶点k，之后更新length += tmp,以及更新cur_vertex = k,如果length大于min，则说明改路径无效，跳出循环。
4）重复步骤3遍历每一个结点。循环结束后，对length更新，加上最后一个结点到cur_vertex结点的距离。这是如果min大于legnth，则对min更新，并把path数组复制到best_path中去。
5）重复步骤2)直至遍历完每个结点。返回最小长度。

//求汉密尔顿回路函数 int Hanmilton(){int path[1000] = {0};int cur_vertex = 0; //作为保存当前结点 int length = 0; //汉密尔顿回路长度int min = 10000; //最小长度 for(int i = 1 ; i < this->Nv+1 ; i++){//对每个顶点为初始点进行比遍历寻找汉密尔顿回路 length = 0; //重新设置最端长度为0 memset(this->isvisited,0,sizeof(this->isvisited[0])*(this->Nv+1)); //重新初始化访问数组为0 this->isvisited[i] = 1; //标记当前结点为已访问 path[1] = i; //保存到临时路径数组的第一个cur_vertex = i; //保存当前顶点for(int j = 2 ; j < this->Nv+1 ; j++){//访问剩余的结点 int k = 0;//寻找到第一个未访问的结点 for(k = 2 ; k < this->Nv+1 ; k++){if(this->isvisited[k] == 0){break;}}int tmp = this->data[cur_vertex][k]; //保存当前顶点到该结点的路径长度 for(int m = k+1 ; m < this->Nv+1 ; m++){//向后寻找有没有路径更短的节点 if((!this->isvisited[m]) && (tmp > this->data[cur_vertex][m])){tmp = this->data[cur_vertex][m];//更新当前最短路径 k = m;//更新第一个未被访问的结点 }}path[j] = k; //保存路径上的结点this->isvisited[k] = 1; //标记为已访问 cur_vertex = k; //跟新当前结点 length += tmp; //跟新长度 if(length > min){ //当前长度大于最小长度，则改路径无效，跳出循环 break;}}length += this->data[cur_vertex][i];if(min > length){ //更新最小长度并保存最佳路径 min = length;for(int m = 0 ; m < this->Nv+1 ; m++){this->best_path[m] = path[m]; }}}//返回最小长度 return min; }

例子

下面的例子是基于如下图结构：

全部代码如下：

#include <iostream> #include <cstring> #include <vector> #include <cstdio> using namespace std;/*边与边长：(起点，终点，长度) 1 2 21 3 31 4 21 5 52 3 62 4 82 5 103 4 103 5 154 5 12 */ class Graph{private:int** data; //邻接矩阵 到sa 拉黑圣诞节， int* isvisited; //访问数组 int Nv; //顶点数 int Ne; //边数vector<int> best_path; //汉密尔顿最佳路径 public://构造函数Graph(int nv,int ne){this->Nv = nv;this->Ne = ne;this->data = new int*[nv+1];best_path.reserve(nv+1);for(int i = 0 ; i < nv+1 ; i++){best_path[i] = 0;}//初始化访问数组 this->isvisited = new int[nv+1];memset(this->isvisited,0,sizeof(this->isvisited[0])*(nv+1));//对邻接矩阵进行初始化 for(int i = 0 ; i < nv+1 ; i++){data[i] = new int[nv+1];memset(data[i],0,sizeof(data[i][0])*(nv+1));}cout<<"请输入边与边长："<<endl;//对边进行初始化 for(int i = 0 ; i < ne ; i++){int v1,v2,weight;cin>>v1>>v2>>weight;this->data[v1][v2] = this->data[v2][v1] = weight;} }//求汉密尔顿回路函数 int Hanmilton(){int path[1000] = {0};int cur_vertex = 0; //作为保存当前结点 int length = 0; //汉密尔顿回路长度int min = 10000; //最小长度 for(int i = 1 ; i < this->Nv+1 ; i++){//对每个顶点为初始点进行比遍历寻找汉密尔顿回路 length = 0; //重新设置最端长度为0 memset(this->isvisited,0,sizeof(this->isvisited[0])*(this->Nv+1)); //重新初始化访问数组为0 this->isvisited[i] = 1; //标记当前结点为已访问 path[1] = i; //保存到临时路径数组的第一个cur_vertex = i; //保存当前顶点for(int j = 2 ; j < this->Nv+1 ; j++){//访问剩余的结点 int k = 0;//寻找到第一个未访问的结点 for(k = 2 ; k < this->Nv+1 ; k++){if(this->isvisited[k] == 0){break;}}int tmp = this->data[cur_vertex][k]; //保存当前顶点到该结点的路径长度 for(int m = k+1 ; m < this->Nv+1 ; m++){//向后寻找有没有路径更短的节点 if((!this->isvisited[m]) && (tmp > this->data[cur_vertex][m])){tmp = this->data[cur_vertex][m];//更新当前最短路径 k = m;//更新第一个未被访问的结点 }}path[j] = k; //保存路径上的结点this->isvisited[k] = 1; //标记为已访问 cur_vertex = k; //跟新当前结点 length += tmp; //跟新长度 if(length > min){ //当前长度大于最小长度，则改路径无效，跳出循环 break;}}length += this->data[cur_vertex][i];if(min > length){ //更新最小长度并保存最佳路径 min = length;for(int m = 0 ; m < this->Nv+1 ; m++){this->best_path[m] = path[m]; }}}//返回最小长度 return min;}//打印最佳汉密尔顿回路 void Print_Best_Path(){cout<<this->best_path[1];for(int i = 2 ; i < this->Nv+1 ; i++){cout<<" -> "<<this->best_path[i];}cout<<" -> "<<this->best_path[1];}//打印邻接矩阵 void Print(){for(int i = 1 ; i < this->Nv+1 ; i++){for(int j = 1 ; j < this->Nv+1 ; j++){printf("%3d",this->data[i][j]);}cout<<endl;}} };int main() {cout<<"请输入顶点数与边数："<<endl;int nv,ne;cin>>nv>>ne;Graph graph(nv,ne);cout<<"邻接矩阵为："<<endl;graph.Print();cout<<"该图的汉密尔顿回路长度为："<<endl;int length = 0;length = graph.Hanmilton();cout<<length<<endl;cout<<"汉密尔顿回路路径为："<<endl;graph.Print_Best_Path(); return 0; }

运行结果如下：

总结

以上是生活随笔为你收集整理的汉密尔顿回路问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。