-
哈密頓迴路
鎖定
- 中文名
- 哈密頓迴路
- 外文名
- Hamiltonian cycle
- 別 名
- 閉合的哈密頓路徑
- 説 明
- 是一個無向圖
- 提出者
- 天文學家哈密頓
哈密頓迴路定義
哈密頓迴路的定義： G=(V,E)是一個圖，若G中一條路徑通過且僅通過每一個頂點一次，稱這條路徑為哈密頓路徑。若G中一個迴路通過且僅通過每一個頂點一次，稱這個環為哈密頓迴路。若一個圖存在哈密頓迴路，就稱為哈密頓圖。
哈密頓迴路由來
哈密頓迴路
這個問題和著名的七橋問題的不同之處在於，七橋問題是經過每條邊一次，而哈密頓問題是經過每個頂點一次。哈密頓問題尋找一條從給定的起點到給定的終點沿途恰好經過所有其他城市一次的路徑。
哈密頓迴路判斷條件
哈密頓圖的必要條件： 若G=(V,E) 是一個哈密頓圖，則對於V的每一個非空子集S，均有W(G－S) ≤|S|。其中|S|是S中的頂點數，W(G－S)表示圖G擦去屬於S中的頂點後，剩下子圖的連通分支的個數。
哈密頓圖的充分條件： 設G=(V,E)是一個無向簡單圖，|V|=n，n≥3。若對於任意的兩個頂點u，v∊V，d(u)+d(v) ≥n，那麼, G是哈密爾頓圖。此條件由美國圖論數學家奧勒在1960年給出。
哈密頓迴路算法
哈密頓路徑問題在上世紀七十年代初，終於被證明是“NP完全”的。據説具有這樣性質的問題，難於找到一個有效的算法。實際上對於某些頂點數不到100的網絡，利用現有最好的算法和計算機也需要比較荒唐的時間（比如幾百年）才能確定其是否存在一條這樣的路徑。
要滿足兩個條件：
⒈封閉的環；
⒉是一個連通圖，且圖中任意兩點可達。
經過圖中所有頂點一次且僅一次的迴路稱為哈密頓迴路。
具有哈密頓迴路的圖稱為哈密頓圖，具有哈密頓通路但不具有哈密頓迴路的圖稱為半哈密頓圖。
平凡圖是哈密頓圖。
⒊若以1到2、2到3、3到4、4到5、5到1，為計數規律，則各點均出現兩次；這種判斷方法在計算機編程運算中顯得尤為重要，其會精簡很多運算過程；
⒋新出爐，有待檢測的代碼如下：
%-------輸入的數據的原數據參照 % v1 v2 v3 v4 v5 %v1 0 20 1 11 2 %v2 0 0 9 1 3 %v3 0 0 0 13 8 %v4 0 0 0 0 6 %v5 0 0 0 0 0 %以上為輸入數據的原數據參照 %建議所計算的數據矩陣長度為5，不會產生bug，且不會對任何計算機造成計算負擔 %輸入數據矩陣長度可以超過5，但是最初計算出的n個最小值中，重複次數超過2的點的種類只允許為一種 a=[0 20 1 11 2 0 0 9 1 3 0 0 0 13 8 0 0 0 0 6 0 0 0 0 0]; l=length(a) s1=inf zp=inf n2=1 f=a f(a==0)=inf b=zeros(l) i1=0 while i1<=l-1 [r c]=find(f==min(min(f))) b(r(1),r(1))=f(r(1),c(1)) f(r(1),c(1))=inf i1=i1+1 end f1=f [rz cz]=find(b>0) pathz=[rz cz] pz=[rz;cz] p2z=zeros（2*l,1） i2z=1 n2z=0 while i2z<=2*l [r2z c2z]=find(pz==pz(i2z,1)) k1z=size(r2z) if k1z(1,1)>2 p2z(r2z,1)=pz(r2z,1) n2z=n2z+1 end i2z=i2z+1 end if n2z==2 HHL=b zp=sum(sum(b)) else while min(min(f1）)~=inf if n2>2 b=snh end [r1 c1]=find(b>0) path1=[r1 c1] p1=[r1;c1] p2=zeros（2*l,1） i2=1 n2=0 while i2<=2*l [r2 c2]=find(p1==p1(i2,1) k1=size(r2) if k1(1,1)>2 p2(r2,1)=p1(r2,1) n2=n2+1 end i2=i2+1 end [r3 c3]=find(p2>0) p3=zeros(l,2) i3=0 while i3<=n2-1 if r3(1)<=l p3(r3(1),:)=path1(r(1),:) else p3(r3(1)-l,:)=path1(r3(1)-l,:) end r3(1)=[] i3=i3+1 end p3(p3==0)=[] p3=reshape(p3,n2,2） p8=p2 [r8 c8]=find(p8>0) p9=p8 r9=r8 i4=1 while i4<=n2 f1(p9(r9(1),1),:)=inf f1(:,p9(r9(1),1))=inf r9(1)=[] i4=i4+1 end [r4 c4]=find(f1==min(min(f1))) f1(r4,c4)=inf b1=b b1(r4,c4)=a(r4,c4) i5=1 p4=p3 while i5<=n2 b1=b b1(r4(1),c4(1))=a(r4(1),c4(1)) b1(p4(1,1),p4(1,2))=0 p4(1,:)=[] [r5 c5]=find(b1>0) p5=[r5;c5] i6=1 n6=0 while i6<=2*l [r6 c6]=find(p5==p5(i6,1)) k6=size(r6） if k6(1,1)>2 n6=n6+1 end i6=i6+1 end if n6>2 if sum(sum(b1))<s1 snh=[] s1=sum(sum(b1）) snh=b1 end else if sum(sum(b1）)<zp HHL=[] zp=sum(sum(b1）) HHL=b1 end end i5=i5+1 end end [rs cs]=find(HHL>0) minpaths=[rs cs] journeys=zp
注：這段代碼採用分支定界法作為編寫程序的依據，因此代碼依舊侷限在算法上；而且代碼的使用對所要計算的數據是有要求的，如下：
⒊代碼擴展方法請使用者獨立思考，不唯一。
⒋運算數據擴展方法，請使用者獨立思考，不唯一。
⒌此代碼為本人畢設的附加產品，不會對使用此代碼者，因理解不當或使用不當而造成的任何不良後果，付出任何責任。
⒍代碼僅供交流。
哈密頓迴路C代碼
#include<stdio.h>
#include<windows.h>
#include<string.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAX_VER_NUM 11//頂點的最大數
#define MAX_ARC_NUM 22//邊的最大數
typedef char VertexType;
typedef int Status;
typedef struct EdgeInfo
{
VertexType v1;
VertexType v2;
int weight;
}EdgeInfo;
typedef struct ArcBox//邊所包含的信息
{
int iver;
struct ArcBox *ilink;
int jver;
struct ArcBox *jlink;
int weight;//權值
int mark;
char *info;
}ArcBox;
typedef struct VerBox//頂點所包含的信息
{
VertexType data;//頂點值
ArcBox *firstedge;//指向鄰接點（邊所包含的信息）
}VerBox;
typedef struct Graph
{
int vernum;//頂點總個數
int arcnum;//邊的總個數
VerBox vertexs[MAX_VER_NUM];//頂點信息
}Graph;
typedef struct StackData//棧中可存放的數據
{
VertexType data;
int lenght;
struct StackData *pnext;
}StackData;
typedef struct Stack//棧用於存放已訪問過的頂點
{
struct StackData *ptop;
struct StackData *pbottom;
}STNODE;
typedef struct Stack_Arc//存方已訪問過的邊及頂點
{
ArcBox *p[MAX_ARC_NUM];
int v_num[MAX_ARC_NUM];
}SANode;
int Visited[MAX_VER_NUM];//標記頂點是否被訪問過
EdgeInfo Data[MAX_ARC_NUM]={{'A','B',324},{'A','J',419},{'A','K',328},{'A','D',241},{'A','C',556},{'A','F',703},{'A','G',521},{'B','G',391},{'B','H',230},{'B','I',356},{'B','J',220},{'C','F',642},{'C','E',337},{'D','F',829},{'D','K',334},{'E','F',581},{'E','G',1254},{'F','G',887},{'G','H',242},{'H','I',249},{'I','J',713},{'J','K',398}};//邊及權值
int Count=0;//記可走邊的總數
STNODE Stack;//存放已訪問過
SANode Store_Arc_Ver;//存放弧的信息及頂點信息
int LAV=-1,ALL=0;
int Short_Len=1000000,Short_Load=0;//存放最斷最路經
void CreateGraph(Graph **G);//創建圖
int LocateVer(Graph G,VertexType v);//查找頂點v在圖中的位置
void ShowAdjInfo(Graph *G);//查看鄰接點信息
int FirstAdjVer(Graph *G,int v,ArcBox **u);//第一鄰接點
int NextAdjVer(Graph *G,int v,int w,ArcBox **u);//下一鄰接點
void NAV(ArcBox *p,int *n,int v,int w,ArcBox **u);//遞歸查找下一鄰接點
void InitArcBox_mark(ArcBox *p);//初始化mark的值
void DFSTraverse(Graph *G);//深度優先遍歷圖
void DFST(Graph *G,int v);//剃歸深度優先遍歷
void InitStack(void);//初始化棧
void Push(VertexType c);//數據進棧
void Pop(void);//出棧
Status IsAdj(int *len,VertexType v);//判斷棧頂的點是否與A為鄰接點
int main()
{
Graph *G=NULL;
CreateGraph(&G);
printf("頂點的鄰接表：\n");
ShowAdjInfo(G);printf("\n\n");
printf("可走路徑結果:\n");
DFSTraverse(G);printf("\n");
printf("可走路徑總數:%d條；最短路徑為:路徑%d，長度為:%d\n\n",ALL,Short_Load,Short_Len);
return 0;
}
void CreateGraph(Graph **G)//創建圖
{
int i,j,k,w;
char v1,v2;
ArcBox *pnew;
(*G)=(Graph *)malloc(1*sizeof(Graph));
if((*G)==NULL)
{
printf("動態內存分配失敗，程序終止！\n");
exit(-1);
}
(*G)->arcnum=MAX_ARC_NUM;
(*G)->vernum=MAX_VER_NUM;
for(i=0;i<(*G)->vernum;i++)
{
(*G)->vertexs[i].data='A'+i;
(*G)->vertexs[i].firstedge=NULL;
}
for(k=0;k<(*G)->arcnum;k++)
{
v1=Data[k].v1;
v2=Data[k].v2;
w=Data[k].weight;
i=LocateVer((**G),v1);
j=LocateVer((**G),v2);
if(i>=0&&j>=0)
{
pnew=(ArcBox *)malloc(1*sizeof(ArcBox));
if(pnew==NULL)
{
printf("動態內存分配失敗，程序終止！\n");
exit(-1);
}
pnew->iver=i;
pnew->jver=j;
pnew->weight=w;
pnew->mark=FALSE;
pnew->ilink=(*G)->vertexs[i].firstedge;
pnew->jlink=(*G)->vertexs[j].firstedge;
(*G)->vertexs[i].firstedge=pnew;
(*G)->vertexs[j].firstedge=pnew;
}
else
{
printf("注意：*****頂點%c不存在！*****\n",i<0?v1:v2);
}
}
return;
}
int LocateVer(Graph G,VertexType v)//查找頂點v在圖中的位置
{
int i,result=-1;
for(i=0;i<MAX_VER_NUM;i++)
{
if(G.vertexs[i].data==v)
{
result=i;
break;
}
}
return result;
}
void ShowAdjInfo(Graph *G)//查看鄰接點信息
{
int v,w;
ArcBox *u;
for(v=0;v<G->vernum;v++)
{
printf("[%d|%c]",v,G->vertexs[v].data);
for(w=FirstAdjVer(G,v,&u);w>=0;w=NextAdjVer(G,v,w,&u))
{
printf("->[%d|%c|%d]",w,G->vertexs[w].data,u->weight);
}
InitArcBox_mark(G->vertexs[v].firstedge);
printf("\n");
}
}
int FirstAdjVer(Graph *G,int v,ArcBox **u)//第一鄰接點
{
int w=-1;
ArcBox *p;
p=G->vertexs[v].firstedge;
(*u)=p;
if(v==p->iver)
{
w=p->jver;
p->mark=TRUE;
}
else if(v==p->jver)
{
w=p->iver;
p->mark=TRUE;
}
return w;
}
int NextAdjVer(Graph *G,int v,int w,ArcBox **u)//下一鄰接點
{
int n=-1;
ArcBox *p;
(*u)=NULL;
p=G->vertexs[v].firstedge;
NAV(p,&n,v,w,&(*u));
return n;
}
void NAV(ArcBox *p,int *n,int v,int w,ArcBox **u)//遞歸查找下一鄰接點
{
if(p->mark==FALSE && (p->iver==v ||p->jver==v))
{
(*u)=p;
if(p->iver==v)
{
*n=p->jver;p->mark=TRUE;
}
else if(p->jver==v)
{
*n=p->iver;p->mark=TRUE;
}
else printf("下一鄰接點數據出錯，請檢查！\n");
}
else
{
if(p->ilink!=NULL && *n==-1)
{
NAV(p->ilink,n,v,w,&(*u));
}
if(p->jlink!=NULL && *n==-1)
{
NAV(p->jlink,n,v,w,&(*u));
}
}
return;
}
void InitArcBox_mark(ArcBox *p)//初始化mark的值
{
p->mark=FALSE;
if(p->ilink!=NULL)
{
InitArcBox_mark(p->ilink);
}
if(p->jlink!=NULL)
{
InitArcBox_mark(p->jlink);
}
return;
}
void DFSTraverse(Graph *G)//深度優先遍歷圖
{
int v;
for(v=0;v<G->vernum;v++)
{
Visited[v]=FALSE;
InitArcBox_mark(G->vertexs[v].firstedge);
}
InitStack();
DFST(G,0);
return;
}
void DFST(Graph *G,int v)//剃歸深度優先遍歷
{
int w=-1,flag=1,i=0,enter=1,len=0;
ArcBox *u;//鄰接點
StackData *p;
Visited[v]=TRUE;
Count++;
Push(G->vertexs[v].data);
if(Count==11&&IsAdj(&len,Stack.ptop->data)==1)
{
ALL++;
printf("路徑%-2d：",ALL);
printf("A");
p=Stack.ptop;
len=len+p->lenght;
if(Short_Len>len) Short_Load=ALL,Short_Len=len;
while(p!=Stack.pbottom)
{
printf("->%c",p->data);
p=p->pnext;
}
printf(" 總長度為：%d",len);
printf("\n");
}
for(w=FirstAdjVer(G,v,&u);w>=0;w=NextAdjVer(G,v,w,&u))
{
enter=1;
for(i=0;i<=LAV;i++)
{
if(Store_Arc_Ver.p[i]==u)
{
enter=0;
break;
}
}
if(enter==1)
{
Store_Arc_Ver.p[++LAV]=u;
Store_Arc_Ver.v_num[LAV]=v;
}
if(Visited[w]==FALSE)
{
DFST(G,w);
Visited[w]=FALSE;
Count--;
Pop();
}
}
for(LAV;Store_Arc_Ver.v_num[LAV]==v&&LAV>=0;)//還原當前頂點邊的狀態並出棧
{
Store_Arc_Ver.p[LAV]->mark=FALSE;
Store_Arc_Ver.p[LAV]=NULL;
LAV--;
}
}
void InitStack(void)//初始化棧
{
Stack.pbottom=Stack.ptop=(StackData *)malloc(1*sizeof(StackData));
Stack.pbottom->pnext=NULL;
return;
}
void Push(VertexType c)//數據進棧
{
StackData *pnew;
char v1,v2;
int i;
pnew=(StackData *)malloc(1*sizeof(StackData));
pnew->data=c;
if(c=='A')
{
pnew->lenght=0;
}
else
{
v1=c;
v2=Stack.ptop->data;
for(i=0;i<MAX_ARC_NUM;i++)
{
if((v1==Data[i].v1 || v1==Data[i].v2) && (v2==Data[i].v1 || v2==Data[i].v2))
{
pnew->lenght=Stack.ptop->lenght+Data[i].weight;
}
}
}
pnew->pnext=Stack.ptop;
Stack.ptop=pnew;
return;
}
void Pop(void)
{
StackData *p;
p=Stack.ptop;
Stack.ptop=p->pnext;
free(p);
}
Status IsAdj(int *len,VertexType v)//判斷是棧頂的點是否與A為鄰接點
{
int i;
for(i=0;i<MAX_ARC_NUM;i++)
{
if((Data[i].v1==v&&Data[i].v2=='A')||(Data[i].v1=='A'&&Data[i].v2==v))
{
*len=Data[i].weight;
return TRUE;
break;
}
}
system("pause");
return FALSE;
}
/*數據的存儲結構為鄰接多重表，解題的思路是深度優遍歷再配合回溯法，代碼僅供學習交流使用。*/
哈密頓迴路C++代碼
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define max(a,b) (a>b?a:b)
using namespace std;
typedef long long(LL);
typedef unsigned long long(ULL);
const double eps(1e-8);
char B[1<<15],*S=B,*T=B,ch;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int aa,bb; int F()
{
while(ch=getc(),(ch<'0'||ch>'9')&&ch!='-'); ch=='-'?aa=bb=0:(aa=ch-'0',bb=1);
while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0'; return bb?aa:-aa;
}
#define N 100010
int n,swp,cnt,z[N]; long long ans;
#define swap(a,b) (swp=a,a=b,b=swp)
#define abs(x) (x>0?x:-(x))
#define max(a,b) (a>b?a:b)
#define cmax(x) (ans<x?ans=x:1)
struct P {int x,y,id,nx,ny;} p[N];
bool operator<(const P&a,const P&b) {return a.nx<b.nx||a.nx==b.nx&&a.ny<b.ny;}
class Graph
{
private:
int et,la[N],ufs[N],tot;
struct D
{
int x,y,v;
bool operator<(const D&a)const {return v<a.v;}
} d[N<<2];
struct E {int to,v,nxt;} e[N<<1];
int gf(int x) {return ufs[x]==x?x:ufs[x]=gf(ufs[x]);}
void adde(int x,int y,int v)
{
e[++et]=(E) {y,v,la[x]},la[x]=et;
e[++et]=(E) {x,v,la[y]},la[y]=et;
}
public:
Graph() {et=1;}
void add(int x,int y,int v) {d[++tot]=(D) {x,y,v};}
void make()
{
std::sort(d+1,d+1+tot);
for(int i=1; i<=n; i++)ufs[i]=i; cnt=n;
for(int i=1,x,y; i<=tot; i++)
if((x=gf(d[i].x))!=(y=gf(d[i].y)))
{
ufs[x]=y,cnt--,ans+=d[i].v,
adde(d[i].x,d[i].y,d[i].v);
}
}
} G;
struct D {int x,n;} d[N];
bool operator<(const D&a,const D&b) {return a.x<b.x;}
#define dis(i,j) (abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y))
void ins(int i)
{
for(int t=p[i].ny; t<=cnt; t+=t&-t)
if(z[t]==0||p[z[t]].x+p[z[t]].y<p[i].x+p[i].y)z[t]=i;
}
int query(int i)
{
int f=0;
for(int t=p[i].ny; t>0; t-=t&-t)
if(z[t]&&(f==0||p[z[t]].x+p[z[t]].y>p[f].x+p[f].y))f=z[t];
return f;
}
void work()
{
for(int i=1; i<=n; i++)p[i].nx=p[i].x-p[i].y,p[i].ny=p[i].y;
std::sort(p+1,p+1+n);
for(int i=1; i<=n; i++)d[i]=(D) {p[i].ny,i};
std::sort(d+1,d+1+n); d[n+1].x=d[n].x; cnt=1;
for(int i=1; i<=n; i++)
{
p[d[i].n].ny=cnt;
if(d[i].x!=d[i+1].x)cnt++;
}
memset(z,0,sizeof(z));
for(int i=1,j; i<=n; ins(i++))
if(j=query(i))G.add(p[i].id,p[j].id,dis(i,j));
}
int main()
{
n=F();
for(int i=1; i<=n; i++)p[i]=(P) {F(),F(),i}; work();
for(int i=1; i<=n; i++)swap(p[i].x,p[i].y); work();
for(int i=1; i<=n; i++)p[i].y=-p[i].y; work();
for(int i=1; i<=n; i++)swap(p[i].x,p[i].y); work(); G.make();
printf("%lld\n",ans);
}
/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-09-11-15.31
* Time: 0MS
* Memory: 137KB
*/
