什么是哈密顿回路

最佳答案:

哈密顿图（哈密尔顿图）（英语：Hamiltonian graph，或Traceable graph）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径（Hamiltonian path）。

详情介绍

哈密顿图（哈密尔顿图）（英语：Hamiltonian graph，或Traceable graph）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径（Hamiltonian path）。

中文名

哈密顿回路

外文名

Hamiltonian cycle

别名

闭合的哈密顿路径

说明

是一个无向图

提出者

天文学家哈密顿

哈密顿回路定义

哈密顿回路的定义： G=(V,E)是一个图，若G中一条路径通过且仅通过每一个顶点一次，称这条路径为哈密顿路径。若G中一个回路通过且仅通过每一个顶点一次，称这个环为哈密顿回路。若一个图存在哈密顿回路，就称为哈密顿图。

哈密顿回路由来

天文学家哈密顿(William Rowan Hamilton) 提出，在一个有多个城市的地图网络中，寻找一条从给定的起点到给定的终点沿 途恰好经过所有其他城市一次的路径。

这个问题和著名的七桥问题的不同之处在于，七桥问题是经过每条边一次，而哈密顿问题是经过每个顶点一次。哈密顿问题寻找一条从给定的起点到给定的终点沿途恰好经过所有其他城市一次的路径。

哈密顿回路判断条件

哈密顿图的必要条件： 若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=;l=length(a)s1=infzp=infn2=1f=af(a==0)=infb=zeros(l)i1=0while i1<=l-1    =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=find(b>0)pathz=pz=p2z=zeros（2*l,1）i2z=1n2z=0while i2z<=2*l    =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    =find(b>0)    path1=    p1=    p2=zeros（2*l,1）    i2=1    n2=0    while i2<=2*l        =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    =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=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=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,:)==find(b1>0)p5=i6=1n6=0while i6<=2*l    =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=find(HHL>0)minpaths=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;//顶点信息}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;    int v_num;}SANode;int Visited;//标记顶点是否被访问过EdgeInfo Data={{'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("nn");    printf("可走路径结果:n");    DFSTraverse(G);printf("n");    printf("可走路径总数:%d条；最短路径为:路径%d，长度为:%dnn",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.data='A'+i;        (*G)->vertexs.firstedge=NULL;    }    for(k=0;k<(*G)->arcnum;k++)    {        v1=Data.v1;        v2=Data.v2;        w=Data.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.firstedge;            pnew->jlink=(*G)->vertexs.firstedge;            (*G)->vertexs.firstedge=pnew;            (*G)->vertexs.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.data==v)        {            result=i;            break;                }    }    return result;}void ShowAdjInfo(Graph *G)//查看邻接点信息{    int v,w;    ArcBox *u;    for(v=0;v<G->vernum;v++)    {        printf("",v,G->vertexs.data);        for(w=FirstAdjVer(G,v,&u);w>=0;w=NextAdjVer(G,v,w,&u))        {            printf("->",w,G->vertexs.data,u->weight);        }        InitArcBox_mark(G->vertexs.firstedge);        printf("n");    }}int FirstAdjVer(Graph *G,int v,ArcBox **u)//第一邻接点{    int w=-1;    ArcBox *p;    p=G->vertexs.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.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=FALSE;        InitArcBox_mark(G->vertexs.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=TRUE;    Count++;    Push(G->vertexs.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==u)            {                enter=0;                break;            }        }        if(enter==1)        {            Store_Arc_Ver.p=u;            Store_Arc_Ver.v_num=v;        }        if(Visited==FALSE)        {                DFST(G,w);            Visited=FALSE;            Count--;            Pop();        }    }    for(LAV;Store_Arc_Ver.v_num==v&&LAV>=0;)//还原当前顶点边的状态并出栈    {        Store_Arc_Ver.p->mark=FALSE;        Store_Arc_Ver.p=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.v1 || v1==Data.v2) && (v2==Data.v1 || v2==Data.v2))            {                    pnew->lenght=Stack.ptop->lenght+Data.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.v1==v&&Data.v2=='A')||(Data.v1=='A'&&Data.v2==v))        {            *len=Data.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,*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; 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;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,ufs,tot;      struct D      {            int x,y,v;            bool operator<(const D&a)const {return v<a.v;}      } d;      struct E {int to,v,nxt;} e;      int gf(int x) {return ufs==x?x:ufs=gf(ufs);}      void adde(int x,int y,int v)      {            e=(E) {y,v,la},la=et;            e=(E) {x,v,la},la=et;      }public:      Graph() {et=1;}      void add(int x,int y,int v) {d=(D) {x,y,v};}      void make()      {            std::sort(d+1,d+1+tot);            for(int i=1; i<=n; i++)ufs=i; cnt=n;            for(int i=1,x,y; i<=tot; i++)                  if((x=gf(d.x))!=(y=gf(d.y)))                  {                        ufs=y,cnt--,ans+=d.v,                                            adde(d.x,d.y,d.v);                  }      }} G;struct D {int x,n;} d;bool operator<(const D&a,const D&b) {return a.x<b.x;}#define dis(i,j) (abs(p.x-p.x)+abs(p.y-p.y))void ins(int i){      for(int t=p.ny; t<=cnt; t+=t&-t)            if(z==0||p].x+p].y<p.x+p.y)z=i;}int query(int i){      int f=0;      for(int t=p.ny; t>0; t-=t&-t)            if(z&&(f==0||p].x+p].y>p.x+p.y))f=z;      return f;}void work(){      for(int i=1; i<=n; i++)p.nx=p.x-p.y,p.ny=p.y;      std::sort(p+1,p+1+n);      for(int i=1; i<=n; i++)d=(D) {p.ny,i};      std::sort(d+1,d+1+n); d.x=d.x; cnt=1;      for(int i=1; i<=n; i++)      {            p.n].ny=cnt;            if(d.x!=d.x)cnt++;      }      memset(z,0,sizeof(z));      for(int i=1,j; i<=n; ins(i++))            if(j=query(i))G.add(p.id,p.id,dis(i,j));}int main(){      n=F();      for(int i=1; i<=n; i++)p=(P) {F(),F(),i}; work();      for(int i=1; i<=n; i++)swap(p.x,p.y); work();      for(int i=1; i<=n; i++)p.y=-p.y; work();      for(int i=1; i<=n; i++)swap(p.x,p.y); work(); G.make();      printf("%lldn",ans);}