哈密顿回路算法.doc

《哈密顿回路算法.doc》由会员分享，可在线阅读，更多相关《哈密顿回路算法.doc（12页珍藏版）》请在三一文库上搜索。

1、哈密顿回路算法概念：哈密顿图：图G的一个回路，若它通过图的每一个节点一次，且仅一次，就是哈密顿回路。存在哈密顿回路的图就是哈密顿图。哈密顿图就是从一点出发，经过所有的必须且只能一次，最终回到起点的路径。图中有的边可以不经过，但是不会有边被经过两次。与欧拉图的区别：欧拉图讨论的实际上是图上关于边的可行便利问题，而哈密顿图的要求与点有关。判定：一：Dirac定理（充分条件）设一个无向图中有N个顶点，若所有顶点的度数大于等于N/2，则哈密顿回路一定存在。（N/2指的是N/2，向上取整）二：基本的必要条件设图G=V， E是哈密顿图，则对于v的任意一个非空子集S，若以|S|表示S中元素的数目，G-S表示

2、G中删除了S中的点以及这些点所关联的边后得到的子图，则W（G-S）=|S|成立。其中W（G-S）是G-S中联通分支数。三：竞赛图（哈密顿通路）N（N=2）阶竞赛图一点存在哈密顿通路。算法：一：在Dirac定理的前提下构造哈密顿回路过程：1：任意找两个相邻的节点S和T，在其基础上扩展出一条尽量长的没有重复结点的路径。即如果S与结点v相邻，而且v不在路径S - T上，则可以把该路径变成v - S - T，然后v成为新的S.从S和T分别向两头扩展，直到无法继续扩展为止，即所有与S或T相邻的节点都在路径S - T上。2：若S与T相邻，则路径S - T形成了一个回路。3：若S与T不相邻，可以构造出来一个

3、回路。设路径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，即形成了一个回路。4：到此为止，已经构造出来了一个没有重复节点的的回路，如果其长度为N，则哈密顿回路就找到了。如果回路的长度小于N，由于整个图是连通的，所以在该回路上，一定存在一点与回路之外的点相邻。那么从该点处把回路断开，就变回了一条路径，同时还可以将与之相邻的点加入路径。再按照步骤1的方法尽量扩展路径，则一定有新的节点被加进来。接着回到路径2.证明：可利用

4、鸽巢原理证明。伪代码：设s为哈密顿回路的起始点，t为哈密顿回路中终点s之前的点.ans为最终的哈密顿回路。倒置的意思指的是将数组对应的区间中数字的排列顺序方向。1：初始化，令s = 1，t为s的任意一个邻接点。2：如果ans中元素的个数小于n，则从t开始向外扩展，如果有可扩展点v，放入ans的尾部，并且t=v，并继续扩展，如无法扩展进入步骤3.3：将当前得到的ans倒置，s和t互换，从t开始向外扩展，如果有可扩展点v，放入ans尾部，并且t=v，并继续扩展。如无法扩展进入步骤4.4：如果当前s和t相邻，进入步骤5.否则，遍历ans，寻找点ansi，使得ansi与t相连并且ansi +与相连，将

5、从ansi + 1到t部分的ans倒置，t=ansi +，进如步骤5.5：如果当前ans中元素的个数等于n，算法结束，ans中保存了哈密顿回路（可看情况是否加入点s）。否则，如果s与t连通，但是ans中的元素的个数小于n，则遍历ans，寻找点ansi，使得ansi与ans外的一点（j）相连，则令s=ansi - 1，t = j，将ans中s到ansi - 1部分的ans倒置，将ans中的ansi到t的部分倒置，将点j加入到ans的尾部，转步骤2.时间复杂度：如果说每次到步骤5算一轮的话，那么由于每一轮当中至少有一个节点被加入到路径S - T中，所以总的轮数肯定不超过n轮，所以时间复杂度为O（n

6、）。空间上由于边数非常多，所以采用邻接矩阵来存储比较适合。代码：const int maxN = 100;inline void reverse（int arvmaxN + 7， int s， int t）/将数组anv从下标s到t的部分的顺序反向int temp;while（s t）temp = arvs;arvs = arvt;arvt = temp;s+;t-;void Hamilton（int ansmaxN + 7， bool mapmaxN + 7maxN + 7， int n）int s = 1， t;/初始化取s为1号点int ansi = 2;int i， j;int w;i

7、nt temp;bool visitmaxN + 7 = false;for（i = 1; i = n; i+） if（mapsi） break;t = i;/取任意邻接与s的点为tvisits = visitt = true;ans0 = s;ans1 = t;while（true）while（true）/从t向外扩展for（i = 1; i = n; i+）if（mapti ansansi+ = i;visiti = true;t = i;break;if（i n） break;w = ansi - 1;/将当前得到的序列倒置，s和t互换，从t继续扩展，相当于在原来的序列上从s向外扩展i

8、= 0;reverse（ans， i， w）;temp = s;s = t;t = temp;while（true）/从新的t继续向外扩展，相当于在原来的序列上从s向外扩展for（i = 1; i = n; i+）if（mapti ansansi+ = i;visiti = true;t = i;break;if（i n） break;if（！mapst）/如果s和t不相邻，进行调整for（i = 1; i ansi - 2; i+）/取序列中的一点i，使得ansi与t相连，并且ansi+1与s相连if（mapansit w = ansi - 1;i+;t = ansi;reverse（ans

9、， i， w）;/将从ansi +到部分的ans倒置/此时s和t相连if（ansi = n） return;/如果当前序列包含n个元素，算法结束for（j = 1; j = n; j+）/当前序列中元素的个数小于n，寻找点ansi，使得ansi与ans外的一个点相连if（visitj） continue;for（i = 1; i ansi - 2; i+）if（mapansij）break;if（mapansij） break;s = ansi - 1;t = j;/将新找到的点j赋给treverse（ans， 0， i - 1）;/将ans中s到ansi-1的部分倒置reverse（ans，

10、 i， ansi - 1）;/将ans中ansi到t的部分倒置ansansi+ = j;/将点j加入到ans尾部visitj = true;二：N（N=2）阶竞赛图构造哈密顿通路N阶竞赛图：含有N个顶点的有向图，且每对顶点之间都有一条边。对于N阶竞赛图一定存在哈密顿通路。数学归纳法证明竞赛图在n = 2时必存在哈密顿路：（1）n = 2时结论显然成立；（2）假设n = k时，结论也成立，哈密顿路为V1， V2， V3， 。， Vk;设当n = k+1时，第k + 1个节点为V（k+1），考虑到V（k+1）与Vi（1=i=k）的连通情况，可以分为以下两种情况。1:Vk与V（k+1）两点之间的弧为

11、Vk， V（k+1），则可构造哈密顿路径V1， V2， Vk， V（k+1）。2:Vk与V（k+1）两点之间的弧为V（k+1），Vk，则从后往前寻找第一个出现的Vi（i=k-1，i=1，-i），满足Vi与V（k+1）之间的弧为Vi，V（k+1），则构造哈密顿路径V1， V2， ， Vi， V（k+1）， V（i+1）， ， V（k）。若没找到满足条件的Vi，则说明对于所有的Vi（1=i=k）到V（k+1）的弧为V（k+1），V（i），则构造哈密顿路径V（k+1）， V1， V2， ， Vk.证毕。竞赛图构造哈密顿路时的算法同以上证明过程。用图来说明：假设此时已经存在路径V1 - V2 - V3

12、 - V4，这四个点与V5的连通情况有16种，给定由0/1组成的四个数，第i个数为0代表存在弧V5，Vi，反之为1，表示存在弧Vi，V5sign=0， 0， 0， 0。很显然属于第二种情况，从后往前寻找不到1，即且不存在弧Vi， V5。则构造哈密顿路：V5 - V1 - V2 - V3 - V4.sign=0， 0， 0， 1。属于第一种情况，最后一个数字为1，即代表存在弧Vi， V5且i=4（最后一个点）则构造哈密顿路： V1 - V2 - V3 - V4 - V5.sign=0， 0， 1， 0。属于第二种情况，从后往前找到1出现的第一个位置为3.构造哈密顿路： V1 - V2 - V3

13、- V5 - V4.sign=0， 0， 1， 1。属于第一种情况，最后一个数字为1，即代表存在弧Vi， V5且i=4（最后一个点）则构造哈密顿路： V1 - V2 - V3 - V4 - V5.sign=0， 1， 0， 0。属于第二种情况，从后往前找到1出现的第一个位置为2.构造哈密顿路： V1 - V2 - V5 - V3- V4.sign=0， 1， 0， 1。属于第一种情况，最后一个数字为1，即代表存在弧Vi， V5且i=4（最后一个点）则构造哈密顿路：V1 - V2 - V3 - V4 - V5.（就不举末尾为1的栗子了）sign=1， 0， 1， 0。属于第二种情况，从后往前找到

14、1出现的第一个位置为3.构造哈密顿路： V1 - V2 - V3 - V5- V4.sign=1， 1， 1， 0。属于第二种情况，从后往前找到1出现的第一个位置为3.构造哈密顿路： V1 - V2 - V3 - V5- V4.sign=1， 1， 1， 1。同样最后一位为1，代表存在Vi， V5且i=4（最后一位）则构造哈密顿路：V1 - V2 - V3 - V4 - V5.以上是当N=4时（N+1=5），用图来阐述算法的过程。注意从后往前找不是找这个点编号之前的点，即不是按照编号来的，而是按照当前哈密顿序列从后往前找的。举个栗子：42 11 33 24 14 24 3第一步ans=1第二步

15、ans=2，1第三步sign=0， 1（map32 = 0，map31 = 1，当前序列为2，1） ，而不是1， 0（1，2），因为存在弧V1， V3和V3， V2。这里需要注意下。代码：#include iostream#include cmath#include cstdio#include cstring#include cstdlib#include algorithm#include queue#include stack#include vectorusing namespace std;typedef long long LL;const int maxN = 200;/The

16、arv length is len， insert key befor arvindexinline void Insert（int arv， int if（index len） index = len;len+;for（int i = len - 1; i = 0; -i）if（i ！= index elsearvi = key; return;void Hamilton（int ansmaxN + 7， int mapmaxN + 7maxN + 7， int n）int ansi = 1;ansansi+ = 1;for（int i = 2; i = n; i+）/第一种情况，直接把当前

17、点添加到序列末尾if（mapiansansi - 1 = 1）ansansi+ = i;elseint flag = 0;for（int j = ansi - 2; j 0; -j）/在当前序列中，从后往前找到第一个满足条件的点j，使得存在Vj，Vi且Vi， Vj+1。if（mapiansj = 1）/找到后把该点插入到序列的第j + 1个点前。flag = 1;Insert（ans， ansi， j + 1， i）;break;if（！flag）Insert（ans， ansi， 1， i）;/否则说明所有点都邻接自点i，则把该点直接插入到序列首端。int main（）/freopen（“i

18、nput.txt”， “r”， stdin）;int t;scanf（“%d”， while（t-）int N;scanf（“%d”， int M = N * （N - 1） / 2;int mapmaxN + 7maxN + 7 = 0;for（int i = 0; i M; i+）int u， v;scanf（“%d%d”， /mapij为1说明j i，且存在弧Vi， Vj，因为插入时只考虑该点之前的所有点的位置，与之后的点没有关系。所以只注重该点与其之前的点的连通情况。if（u v）mapvu = 1;int ansmaxN + 7 = 0;Hamilton（ans， map， N）;f

19、or（int i = 1; i = N; i+）printf（i = 1 ？ “%d”：“ %d”， ansi）;printf（“n”）;return 0;代码2:void Hamilton（int ansmaxN + 7， int mapmaxN + 7maxN + 7， int n）int nxtmaxN + 7;memset（nxt， -1， sizeof（nxt）;int head = 1;for（int i = 2; i = n; i+）if（mapihead）nxti = head;head = i;elseint pre = head， pos = nxthead;while（p

20、os ！= -1 pre = pos;pos = nxtpre;nxtpre = i;nxti = pos;int cnt = 0;for（int i = head; i ！= -1; i = nxti）ans+cnt = i;代码三：void Hamitton（bool reachN + 7N + 7， int n）vector int ans;ans.push_back（1）;for（int i=2;i = n;i+）bool cont = false;for（int j=0;j（int）ans.size（）-1;j+）if（reach ansj i ans.insert（ans.begin（）+j+1，i）;cont = true;break;if（cont）continue;if（reach ans.back（） i）ans.push_back（i）;elseans.insert（ans.begin（），i）;for（int i=0;in;i+）printf（“%d%c”，ansi，i=n-1？n： ）;