哈密頓迴路

哈密頓迴路

哈密頓圖(哈密爾頓圖)(英語:Hamiltonian graph,或Traceable graph)是一個無向圖,由天文學家哈密頓提出,由指定的起點前往指定的終點,途中經過所有其他節點且只經過一次。在圖論中是指含有哈密頓迴路的圖,閉合的哈密頓路徑稱作哈密頓迴路(Hamiltonian cycle),含有圖中所有頂點的路徑稱作哈密頓路徑(Hamiltonian path)。

基本介紹

  • 中文名:哈密頓迴路
  • 外文名:Hamiltonian cycle
  • 說明:是一個無向圖
  • 提出者:天文學家哈密頓
由來,算法,C代碼,C++代碼,

由來

天文學家哈密頓(William Rowan Hamilton) 提出,在一個有多個城市的地圖網路中,尋找一條從給定的起點到給定的終點沿 途恰好經過所有其他城市一次的路徑。
哈密頓迴路哈密頓迴路
這個問題和著名的七橋問題的不同之處在於,過橋只需要確定起點,而不用確定終點。哈密頓問題尋找一條從給定的起點到給定的終點沿 途恰好經過所有其他城市一次的路徑。

算法

哈密頓路徑問題在上世紀七十年代初,終於被證明是“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 20 0 9 1 30 0 0 13 80 0 0 0 60 0 0 0 0];l=length(a)s1=infzp=infn2=1f=af(a==0)=infb=zeros(l)i1=0while 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+1endf1=f[rz cz]=find(b>0)pathz=[rz cz]pz=[rz;cz]p2z=zeros(2*l,1)i2z=1n2z=0while 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+1endif n2z==2    HHL=b    zp=sum(sum(b))elsewhile 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+1endp3(p3==0)=[]p3=reshape(p3,n2,2)p8=p2[r8 c8]=find(p8>0)p9=p8r9=r8i4=1while i4<=n2    f1(p9(r9(1),1),:)=inf    f1(:,p9(r9(1),1))=inf    r9(1)=[]    i4=i4+1end[r4 c4]=find(f1==min(min(f1)))f1(r4,c4)=infb1=bb1(r4,c4)=a(r4,c4)i5=1p4=p3while i5<=n2b1=bb1(r4(1),c4(1))=a(r4(1),c4(1))b1(p4(1,1),p4(1,2))=0p4(1,:)=[][r5 c5]=find(b1>0)p5=[r5;c5]i6=1n6=0while i6<=2*l    [r6 c6]=find(p5==p5(i6,1))    k6=size(r6)    if k6(1,1)>2        n6=n6+1    end    i6=i6+1endif n6>2    if sum(sum(b1))<s1        snh=[]        s1=sum(sum(b1))        snh=b1    endelse    if sum(sum(b1))<zp        HHL=[]        zp=sum(sum(b1))        HHL=b1    endendi5=i5+1endend[rs cs]=find(HHL>0)minpaths=[rs cs]journeys=zp
註:這段代碼採用分支定界法作為編寫程式的依據,因此代碼依舊局限在算法上;而且代碼的使用對所要計算的數據是有要求的,如下:
⒈只要數據在開始計算出的n個最小值中,其重複次數超過2次的點的種類只能為一種,例如:代碼段中的數據五個最小值中其重複次數超過2次的點只有v5。
⒉數據矩陣格式要求:只允許為上三角矩陣,不支持全矩陣以及下三角矩陣的運算。
⒊代碼擴展方法請使用者獨立思考,不唯一。
⒋運算數據擴展方法,請使用者獨立思考,不唯一。
⒌此代碼為本人畢設的附加產品,不會對使用此代碼者,因理解不當或使用不當而造成的任何不良後果,付出任何責任。
⒍代碼僅供交流。

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 100010int 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*/

相關詞條

熱門詞條

聯絡我們