汉密尔顿回路问题
概述
这是自己这学期算法课的实验作业。下面给出汉密尔顿图的定义。定义如下：对于连通图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 2
1 3 3
1 4 2
1 5 5
2 3 6
2 4 8
2 5 10
3 4 10
3 5 15
4 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;
}运行结果如下：
这里写图片描述
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录