图论 —— 图的遍历 —

本文主要是介绍图论 —— 图的遍历 —— 哈密顿问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【基本概念】

哈密尔顿通路：经过图中每个结点且仅经过一次的通路。
哈密尔顿回路：经过图中每个结点且仅经过一次的回路。
哈密尔顿图：存在哈密尔顿回路的图。
竞赛图：每对顶点之间都有一条边相连的有向图，n 个顶点的竞赛图称为 n 阶竞赛图。
与欧拉回路的对比：欧拉回路是指不重复地走过所有路径的回路；哈密尔顿回路是指不重复地走过所有点并且最后回到起点的回路。

【判定】

1.哈密尔顿通路的判定

设一无向图有 n 个顶点，u、v 为图中任意不相邻的两点，deg(x) 代表 x 的度数

若 $deg(u)+deg(v)\geqslant n-1$ 成立，则图中存在哈密尔顿通路

2.哈密尔顿回路的判定：Dirac 定理

设一无向图有 n 个顶点，u、v 为图中任意不相邻的两点，deg(x) 代表 x 的度数

若 $deg(u)+deg(v)\geqslant n$ ，则图中存在哈密尔顿回路

推论：对于 $n \geqslant 3$ 的无向图，若其任一一点 u 的度数 $deg(u)\geqslant \frac n2$ ，则图中存在哈密尔顿回路

3.竞赛图

对于 $n \geqslant 2$ 的竞赛图，一定存在哈密尔顿通路

【dfs 搜索求哈密尔顿回路】

以每个点为起点进行搜索，直到形成回路

#include <iostream>  
#include <cstring>  
#define N 101
using namespace std;  
int n,m;
int u,v;
int g[N][N];
int vis[N],appear[N];
int ans[N],num[N];
int length;void dfs(int last,int i)//last表示上次访问的点 
{  vis[i]=1;//标记为已经访问过  appear[i]=1;//标记为已在一张图中出现过  ans[length++]=i;//记录答案  for(int j=1;j<=num[i];j++)  {  if(g[i][j]==x&&g[i][j]!=last)//回到起点构成哈密顿环  {   ans[++length]=g[i][j];//存储答案for(int i=1;i<=length-1;i++) //找到了一个环，输出anscout<<ans[i]<<' ';  cout<<ans[length]<<endl;length--;//长度-1break;}  if(!vis[g[i][j]])//遍历与i相关联的所有未访问的点。  dfs(i,g[i][j]); }  length--;  vis[i]=0;//回溯
}  
int main()  
{  memset(vis,0,sizeof(vis));  memset(appear,0,sizeof(appear));  cin>>n>>m; //读入点数与边数for(int i=1;i<=m;i++){   cin>>u>>v; //读入两点g[u][++num[v]]=v;//记录u-v的边g[v][++num[u]]=u;//记录v-u的边}  for(x=1;x<=n;x++) //枚举每一个点，将其作为起点来尝试访问{  if(!appear[x])//如果点x不在之前曾经被访问过的图里  {  length=0;//记录答案的长度  dfs(0,x);  }  }  return 0;  
}

【Dirac 定理下构造无向图的哈密顿回路】

1.过程

任意找两个相邻的节点 S 和 T，在其基础上扩展出一条尽量长的没有重复结点的路径，即如果 S 与结点 v 相邻，而且 v 不在路径 S -> T 上，则可以把该路径变成 v -> S -> T，然后 v 成为新的 S。从 S 和 T 分别向两头扩展，直到无法继续扩展为止，即所有与 S 或 T 相邻的节点都在路径 S -> T 上
若 S 与 T 相邻，则路径 S -> T 形成了一个回路
若 S 与 T 不相邻，可以构造出来一个回路。设路径 S -> T 上有 k+2 个节点，依次为 S, v1, v2, ..., vk, T。可以证明存在节点 vi(i属于[1, k])，满足 vi 与 T 相邻，且 vi+1 与 S 相邻，找到这个节点 vi，把原路径变成 S -> vi -> T -> vi+1 -> S，即形成了一个回路.
到此为止，已经构造出来了一个没有重复节点的的回路，如果其长度为 N，则哈密顿回路就找到了。如果回路的长度小于 N，由于整个图是连通的，所以在该回路上，一定存在一点与回路之外的点相邻。那么从该点处把回路断开，就变回了一条路径，同时还可以将与之相邻的点加入路径。再按照步骤 1 的方法尽量扩展路径，则一定有新的节点被加进来，接着回到路径 2

2.伪代码

设 s 为哈密顿回路的起始点，t 为哈密顿回路中终点 s 之前的点，ans[] 为最终的哈密顿回路

初始化，令 s = 1，t 为 s 的任意一个邻接点.
如果 ans[] 中元素的个数小于 n，则从 t 开始向外扩展，如果有可扩展点 v，放入 ans[] 的尾部，并且 t=v，并继续扩展，如无法扩展进入步骤 3
将当前得到的 ans[] 倒置，s 和 t 互换，从 t 开始向外扩展，如果有可扩展点 v，放入 ans[] 尾部，并且 t=v，并继续扩展，如无法扩展进入步骤 4
如果当前 s 和 t 相邻，进入步骤 5，否则，遍历 ans[]，寻找点 ans[i]，使得 ans[i] 与 t 相连并且 ans[i +１] 与 s 相连，将从 ans[i+1] 到 t 部分的 ans[] 倒置，t=ans[i+1]，进入步骤 5
如果当前 ans[] 中元素的个数等于 n，算法结束，ans[] 中保存了哈密顿回路(可看情况是否加入点 s)，否则，如果 s 与 t 连通，但是 ans[] 中的元素的个数小于 n，则遍历 ans[]，寻找点 ans[i]，使得 ans[i] 与 ans[] 外的一点(j)相连，则令 s=ans[i-1]，t=j，将 ans[] 中 s 到 ans[i-1] 部分的 ans[] 倒置，将 ans[] 中的 ans[i] 到 t 的部分倒置，将点 j 加入到 ans[] 的尾部，转步骤 2

3.时间复杂度

如果说每次到步骤 5 算一轮的话，那么由于每一轮当中至少有一个节点被加入到路径 S -> T 中，所以总的轮数肯定不超过 n 轮，所以时间复杂度为O(n^2)

空间上由于边数非常多，所以采用邻接矩阵来存储比较适合

4.实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<ctime>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 1001
#define MOD 16007
#define E 1e-6
#define LL long long
using namespace std;
bool G[N][N];
bool vis[N];
int ans[N];void Reverse(int arv[N],int s,int t){//将数组anv从下标s到t的部分的顺序反向int temp;while(s<t){swap(arv[s],arv[t]);s++;t--;}
}void Hamilton(int n){int t;int s=1;//初始化取s为1号点for(int i=1;i<=n;i++)if(G[s][i]){t=i;//取任意邻接与s的点为tbreak;}memset(vis,false,sizeof(vis));vis[s]=true;vis[t]=true;ans[0]=s;ans[1]=t;int ansi=2;while(true){//从t向外扩展while(true){int i;for(i=1;i<=n;i++){if(G[t][i] && !vis[i]){ans[ansi++]=i;vis[i]=true;t=i;break;}}if(i>n)break;}//将当前得到的序列倒置Reverse(ans,0,ansi-1);//s和t互换swap(s,t);while(true){//从t继续扩展,相当于在原来的序列上从s向外扩展int i;for(i=1;i<=n;i++){if(G[t][i] && !vis[i]){ans[ansi++]=i;vis[i]=true;t=i;break;}}if(i>n)break;}//如果s和t不相邻,进行调整if(!G[s][t]){//取序列中的一点i,使得ans[i]与t相连,并且ans[i+1]与s相连int i;for(i=1;i<ansi-2;i++)if(G[ans[i]][t]&&G[s][ans[i+1]])break;i++;t=ans[i];Reverse(ans,i,ansi-1);//将从ans[i+1]到ｔ部分的ans[]倒置}//此时s和t相连//如果当前序列包含n个元素,算法结束if(ansi==n)return;//当前序列中元素的个数小于n,寻找点ans[i],使得ans[i]与ans[]外的一个点相连int i,j;for(j=1;j<=n;j++){if(vis[j])continue;for(i=1;i<ansi-2;i++)if(G[ans[i]][j])break;if(G[ans[i]][j])break;}s=ans[i-1];t=j;//将新找到的点j赋给tReverse(ans,0,i-1);//将ans[]中s到ans[i-1]的部分倒置Reverse(ans,i,ansi-1);//将ans[]中ans[i]到t的部分倒置ans[ansi++]=j;//将点j加入到ans[]尾部vis[j]=true;}
}int main(){int n,m;while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){n*=2;for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){if(i==j){G[i][j]=false;G[j][i]=false;}else{G[i][j]=true;G[j][i]=true;}}}int ansi=0;memset(ans, 0, sizeof(ans));for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);G[y][x]=false;G[x][y]=false;}Hamilton(n);for(int i=0;i<n;i++)printf("%d ", ans[i]);printf("\n");}return 0;
}

【N 阶竞赛图下构造有向图的哈密顿通路】

含有N个顶点的有向图，且每对顶点之间都有一条边的图，一定存在哈密顿通路

int ans[105];
int map[105][105];
void Insert(int arv[], int &len, int index, int key){if(index>len)index=len;len++;for(int i=len-1; i>=0; i--){if(i!=index && i)arv[i]=arv[i-1];else{arv[i]=key;return;}}
}
void Hamilton(int n){int ansi = 1;ans[ansi++] = 1;for(int i=2; i<=n; i++){//第一种情况,直接把当前点添加到序列末尾if(map[i][ans[ansi-1]]==1)ans[ansi++]=i;else{int flag=0;//当前序列从后往前找到第一个满足条件的点j,使得存在<Vj,Vi>且<Vi,Vj+1>.for(int j=ansi-2; j>0; j--){if(map[i][ans[j]]==1){//找到后把该点插入到序列的第j+1个点前.flag=1;Insert(ans,ansi,j+1,i);break;}}if(!flag)//否则说明所有点都邻接自点i,则把该点直接插入到序列首端.Insert(ans,ansi,1,i);}}
}
int main(){int n,m;scanf("%d", &n);m=n*(n-1)/2;for(int i=0;i<m;i++){int u,v;scanf("%d%d",&u,&v);if(u<v)map[v][u]=1;}Hamilton(n);for(int i=1;i<=n;i++)printf(i==1? "%d":" %d",ans[i]);printf("\n");return 0;
}

这篇关于图论 —— 图的遍历 —— 哈密顿问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！