图论算法(C++版)课件

1、第四章 图论算法 一对一和一对多的结构：一对一和一对多的结构： 在前边讲解的线性表中，每个元素之间只有一个直接前驱在前边讲解的线性表中，每个元素之间只有一个直接前驱和一个直接后继，在树形结构中，数据元素之间是层次关和一个直接后继，在树形结构中，数据元素之间是层次关系，并且每一层上的数据元素可能和下一层中多个元素相系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关。关，但只能和上一层中一个元素相关。 图结构：是研究数据元素之间的多对多的关系。在这种结构中，任意两个元素之间可能存在关系。即结点之间的关系可以是任意的，图中任意元素之间都可能相关。 图的应用极为广泛，已

2、渗入到诸如语言学、逻辑学、物理、化学、电讯、计算机科学以及数学的其它分支。一、图的定义及其术语一、图的定义及其术语 图（图（Graph）是由顶点的有穷非空集合和顶点之间边的集合）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：组成，通常表示为：G(V,E)，其中，其中，G表示一个图，表示一个图，V是图是图G中顶点的集合，中顶点的集合，E是图是图G中边的集合。中边的集合。 对于图的定义，我们需要明确几个注意的地方： 线性表中我们把数据元素叫元素，树中叫结点，在图中数据元素我们则称之为顶点(Vertex)。 线性表可以没有数据元素，称为空表，树中可以没有结点，叫做空树，而图结构在国内大部

3、分的教材中强调顶点集合V要有穷非空。 线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，而图结构中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。图的各种定义 无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边(Edge)，用无序偶数对(Vi,Vj)来表示。 无向图：图中所有顶点间的边均是无向的。上图上图G1是一个无向图，是一个无向图，G1=V1,E1，其中，其中V1=A,B,C,D，E1=(A,B),(B,C),(C,D),(D,A),(A,C)无序对无序对(A,B) 表示表示A和和B之间的一条之间的一条边边(Edge)，

4、因此，因此(A,B) 和和(B,A)代表的是同一条边。代表的是同一条边。上图上图G2是一个无向图，是一个无向图，G2=V2,E2，其中，其中V2=A,B,C,D，E2=,有向边：若从顶点有向边：若从顶点Vi到到Vj的边有方向，则称这条边为的边有方向，则称这条边为有向边，也称为弧有向边，也称为弧(Arc)，用有序偶数对，用有序偶数对来表来表示，示，Vi称为弧尾，称为弧尾，Vj称为弧头。称为弧头。 有向图：图中所有顶点间的边均是有向的。有向图：图中所有顶点间的边均是有向的。简单图：在图结构中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。以下两个则不属于简单图：稀疏图、稠密

5、图、权稀疏图、稠密图、权有很少边或弧的图（有很少边或弧的图（enn）的图称为稀疏图，反之称为稠密图。）的图称为稀疏图，反之称为稠密图。权权(Weight)：与图的边和弧相关的数。权可以表示从一个顶点到：与图的边和弧相关的数。权可以表示从一个顶点到另一个顶点的距离或耗费。另一个顶点的距离或耗费。带权的图通常称为网带权的图通常称为网(Network)。无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有n*(n-1)/2条边。有向完全图：在有向图中，如果有向完全图：在有向图中，如果任意两个顶点之间都存在方向互任意两个顶点之间都存在方向互为相反的两条

6、弧，则称该图为有为相反的两条弧，则称该图为有向完全图。向完全图。含有含有n个顶点的有向完全图有个顶点的有向完全图有n*(n-1)条边。条边。假设有两个图假设有两个图G1=(V1,E1)和和G2=(V2,E2)，如果，如果V2V1，E2E1，则称，则称G2为为G1的子图的子图(Subgraph)。图的顶点与边之间的关系 对于无向图G=(V,E)，如果边(V1,V2)E，则称顶点V1和V2互为邻接点(Adjacent)，即V1和V2相邻接。 边(V1,V2)依附(incident)于顶点V1和V2，或者说边(V1,V2)与顶点V1和V2相关联。 顶点V的度(Degree)是和V相关联的边的数目，记

7、为TD(V)，如下图，顶点A与B互为邻接点，边(A,B)依附于顶点A与B上，顶点A的度为3。对于有向图G=(V,E)，如果有E，则称顶点V1邻接到顶点V2，顶点V2邻接自顶点V1。以顶点V为头的弧的数目称为V的入度(InDegree)，记为ID(V)，以V为尾的弧的数目称为V的出度(OutDegree)，记为OD(V)，因此顶点V的度为TD(V)=ID(V)+OD(V)。 下图顶点A的入度是2，出度是1，所以顶点A的度是3。路径(Path)、路径长度、回路(Cycle) ：对无向图G=(V，E)，若从顶点vi经过若干条边能到达vj，称顶点vi和vj是连通的，又称顶点vi到vj有路径。 对有向图

8、G=(V，E)，从顶点vi到vj有有向路径，指的是从顶点vi经过若干条有向边(弧)能到达vj。在一条路径中，若没有重复相同的顶点，该路径称为简单路径；第一个顶点和最后一个顶点相同的路径称为回路(环)；在一个回路中，若除第一个与最后一个顶点外，其余顶点不重复出现的回路称为简单回路(简单环)。如果G是有向图，则路径也是有向的。下图用红线列举顶点B到顶点D的两种路径，而顶点A到顶点B就不存在路径。路径的长度是路径上的边或弧的数目。路径的长度是路径上的边或弧的数目。第一个顶点到最后一个顶点相同的路径称为回路或环第一个顶点到最后一个顶点相同的路径称为回路或环(Cycle)。右图用红线列举了从顶点右图用红

9、线列举了从顶点B到顶到顶点点D的四种不同路径：的四种不同路径：连通图 在无向图G中，如果从顶点V1到顶点V2有路径，则称V1和V2是连通的，如果对于图中任意两个顶点Vi和Vj都是连通的，则称G是连通图(ConnectedGraph)下图左侧不是连通图，右侧是连通图：无向图中的极大连通子图称为连通分量。无向图中的极大连通子图称为连通分量。注意以下概念：注意以下概念：首先要是子图，并且子图是要连通的；首先要是子图，并且子图是要连通的；连通子图含有极大顶点数；连通子图含有极大顶点数；“极大极大”的含义：指的是对子的含义：指的是对子图再增加图图再增加图G中的其它顶点，子图就不再连通。中的其它顶点，子图

10、就不再连通。具有极大顶点数的连通子图包含依附于这些顶点的所有边。具有极大顶点数的连通子图包含依附于这些顶点的所有边。在有向图G中，如果对于每一对Vi到Vj都存在路径，则称G是强连通图。有向图中的极大强连通子图称为有向图的强连通分量。下图左侧并不是强连通图，右侧是。并且右侧是左侧的极下图左侧并不是强连通图，右侧是。并且右侧是左侧的极大强连通子图，也是左侧的强连通分量。大强连通子图，也是左侧的强连通分量。二、图的存储结构图的存储结构比较复杂，其复杂性主要表现在： 任意顶点之间可能存在联系，无法以数据元素在存储区中的物理位置来表示元素之间的关系。 图中顶点的度不一样，有的可能相差很大，若按度数最大的

11、顶点设计结构，则会浪费很多存储单元，反之按每个顶点自己的度设计不同的结构，又会影响操作。 图的常用的存储结构有：邻接矩阵、邻接链表、十字链表、邻接多重表和边表。 1.二维数组邻接矩阵存储基本思想：对于有n个顶点的图，用一维数组vexsn存储顶点信息，用二维数组Ann存储顶点之间关系的信息。该二维数组称为邻接矩阵。在邻接矩阵中，以顶点在vexs数组中的下标代表顶点，邻接矩阵中的元素Aij存放的是顶点i到顶点j之间关系的信息。定义int G101101;Gij的值，表示从点i到点j的边的权值，定义如下：上图中的3个图对应的邻接矩阵分别如下： 0 1 1 1 0 1 1 5 8 3G（A）= 1 0

12、 1 1 G（B）= 0 0 1 5 2 6 1 1 0 0 0 1 0 G（C）= 8 2 10 4 1 1 0 0 10 11 3 6 4 11 另外有向图是有讲究的，要考另外有向图是有讲究的，要考虑入度和出度，顶点虑入度和出度，顶点V1的入度的入度为为1，正好是第，正好是第V1列的各数之列的各数之和，顶点和，顶点V1的出度为的出度为2，正好，正好是第是第V1行的各数之和。行的各数之和。 下面是建立图的邻接矩阵的参考程序段：#include#includeusing namespace std;using namespace std;int i,j,k,e,n;int i,j,k,e,n;

13、double g101101;double g101101;double w;double w;int main()int main() int i,j; int i,j; for (i = 1; i = n; i+) for (i = 1; i = n; i+) for (j = 1; j = n; j+) for (j = 1; j e; cin e; for (k = 1; k = e; k+) for (k = 1; k i j w; cin i j w; /读入两个顶点序号及权值读入两个顶点序号及权值 gij = w; gij = w; /对于不带权的图对于不带权的图gij=1gij

14、=1 gji = w; gji = w; /无向图的对称性无向图的对称性, ,如果是有向图则不要有这句！如果是有向图则不要有这句！ return 0; return 0; 建立邻接矩阵时，有两个小技巧: 初始化数组大可不必使用两重初始化数组大可不必使用两重forfor循环。循环。 1) 1) 如果是如果是intint数组，采用数组，采用memset(g, 0 x7f, sizeof(g)memset(g, 0 x7f, sizeof(g)可可全部初始化为一个很大的数全部初始化为一个很大的数( (略小于略小于0 x7fffffff)0 x7fffffff)， 使用使用memset(g, 0, s

15、izeof(g)memset(g, 0, sizeof(g)，全部清为，全部清为0 0， 使用使用memset(g, 0 xaf, sizeof(g)memset(g, 0 xaf, sizeof(g)，全部初始化为一个很，全部初始化为一个很小的数。小的数。 2)2)如果是如果是doubledouble数组，采用数组，采用memset(g,127,sizeof(g);memset(g,127,sizeof(g);可可全部初始化为一个很大的数全部初始化为一个很大的数1.381.38* *1030610306， 使用使用memset(g, 0, sizeof(g)memset(g, 0, size

16、of(g)全部清为全部清为0.0.2.数组模拟邻接表存储数组模拟邻接表存储邻接矩阵看上去是个不错的选择，首先是容易理解，第二是索引和编排都很舒服邻接矩阵看上去是个不错的选择，首先是容易理解，第二是索引和编排都很舒服但是我们也发现，邻接矩阵适合于结点数较少的稠密图。如果用来表示稀疏图，但是我们也发现，邻接矩阵适合于结点数较少的稠密图。如果用来表示稀疏图，则会造成很大的空间浪费。则会造成很大的空间浪费。因此我们可以考虑另外一种存储结构方式，例如把数组与链表结合一起来存储，因此我们可以考虑另外一种存储结构方式，例如把数组与链表结合一起来存储，这种方式在图结构也适用，我们称为邻接表这种方式在图结构也适

17、用，我们称为邻接表(AdjacencyList)。 基本思想：基本思想：对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。信息。每一个单链表设一个表头结点。每一个单链表设一个表头结点。第第i个单链表表示依附于顶点个单链表表示依附于顶点Vi的边的边(对有向图是以顶点对有向图是以顶点Vi为头或尾的弧为头或尾的弧)。图的邻接表存储法，又叫链式存储法。本来是要用链表实现的，但大多数情况下图的邻接表存储法，又叫链式存储法。本来是要用链表实现的，但大多数情况下只要用数组模拟即可。只要用数组模拟即可。 邻接表（有向图） 邻接表的处理

18、方法是这样： 图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。 图中每个顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以我们选择用单链表来存储。若是有向图，邻接若是有向图，邻接表结构就是这样定表结构就是这样定义的。义的。有向图的邻接表：我们先来看下把顶点当弧尾建立的邻接表，这样很容易就可以得到每个顶点的出度： 但也有时为了便于确定顶点的入度或以顶点为弧头的弧，我们可以建立一个有向图但也有时为了便于确定顶点的入度或以顶点为弧头的弧，我们可以建立一个有向图的逆邻接表：的逆邻接表：此时我们很容易就可以算此时我们很容易就可以算出某

19、个顶点的入度或出度出某个顶点的入度或出度是多少，判断两顶点是否是多少，判断两顶点是否存在弧也很容易实现。存在弧也很容易实现。对于带权值的网图，可以在边表结点定义中再对于带权值的网图，可以在边表结点定义中再增加一个数据域来存储权值即可：增加一个数据域来存储权值即可：邻接表（网）邻接表（网）在进行邻接表的输入时，可以直接使用邻接表的定义方式直接输入；在进行邻接表的输入时，可以直接使用邻接表的定义方式直接输入；也可由别的输入方式进行演变，课本上的就是利用边的顶点及其权值进行输入的也可由别的输入方式进行演变，课本上的就是利用边的顶点及其权值进行输入的 以下是用数组模拟邻接表存储的参考程序段：const

20、 int N=maxn； / maxn表示图中最大顶表示图中最大顶点数点数const int E=maxe ； / maxe图中最大边数图中最大边数struct Edgeint u,v; /边所邻接的两个顶点边所邻接的两个顶点int w; /边的权值边的权值int next; /边指针，指向下一条边的内存地址边指针，指向下一条边的内存地址edgeE; / 静态内存，用于分配边静态内存，用于分配边int headN; / 表头表头int num; / 内存的指针内存的指针void init()for(int i=0;iE;i+) headi=-1; /这里为什么这里为什么要设为要设为-1num=

21、 0;void addedge(int b,int e,int w)edgenum.u=b;edgenum.v=e;edgenum.w=w;edgenum.next=headb;headb=num+;int main()num_edge=0;scanf(%d %d,&n,&m); /读入点数和边数for(int i=1;i=m;i+) scanf(%d %d %d,&a,&b,&x); /a、b之间有一条长度为x的边 add_edge(a,b,x);for(int i=head1;i!=0;i=edgei.next) /遍历从点1开始的所有边 /./.return 0;两种方法各有用武之地，需

22、按具体情况，具体选用。课本上的程序段课本上的程序段#include using namespace std;const int maxn=1001,maxm=100001;struct Edgeint next; /下一条边的编号下一条边的编号 int to; /这条边到达的点这条边到达的点 int dis; /这条边的长度这条边的长度 edgemaxm;int headmaxn,num_edge,n,m,u,v,d;void add_edge(int from,int to,int dis) /加入一条从加入一条从from到到to距离为距离为dis的单向边的单向边 edge+num_edge

23、.next=headfrom;edgenum_edge.to=to;edgenum_edge.dis=dis;headfrom=num_edge;int main()for(int i=1;i=m;i+) scanf(%d %d %d,&a,&b,&x); /a、b之间有一条长度为之间有一条长度为x的边的边 add_edge(a,b,x);for(int i=head1;i!=0;i=edgei.next) /遍历从点遍历从点1开始的所有边开始的所有边 【例题】求一个有向图中指定顶点的出度【问题描述】如题【文件输入】第1行：2个空格分开的整数n(2=n=200)和m(10=m=20000)，分

24、别表示图的顶点数和边数。第2.m+1行：每行2个空格分开的整数i，j，i表示一条边的起点，j表示终点。第m2行：1个整数k(2=k=n),表示指定的顶点。【文件输出】只有一行为1个整数，表示顶点k的出度。【样例输入】5835454323544142244【样例输出】4【参考代码】 【方法1】邻接矩阵存储图 #include usingnamespacestd; inta201201,n,m,ans=0,x; voidinit() inti,j,k; cinnm; for(i=1;ijk;ajk=1; intmain() init(); cink; for(inti=1;i=n;i+)if(ak

25、i)ans+; coutansendl; 【方法2】邻接表存储图#includeusing namespace std;struct Edge int to,next;w20005;int hMaxn=0,i,x,y,z,n,e,k,cnt,ans=0;void AddEdge(int x,int y) cnt+; wcnt.to=y; wcnt.next=hx; hx=cnt;int main() cinne;/读入顶点数目和边数 for(i=1;ixy; AddEdge(x,y); /建图 cink; for(int p=hk;p!=0;p=wp.next) ans+; coutansen

26、dl;第二节 图的遍历 一、深度优先与广度优先遍历 从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。为了避免重复访问某个顶点，可以设一个标志数组visitedi，未访问时值为false，访问一次后就改为true。 图的遍历分为深度优先遍历和广度优先遍历两种方法，两者的时间效率都是O(n*n)。 1.深度优先遍历深度优先搜索深度优先搜索(Depth First Search-DFS)遍历类似树的先序遍历，是树遍历类似树的先序遍历，是树的先序遍历的推广。的先序遍历的推广。1 算法思想算法思想设初始状态时图中的所有顶点未被访问，则：设初始状态时图中的所

27、有顶点未被访问，则： ：从图中某个顶点：从图中某个顶点vi出发，访问出发，访问vi；然后找到；然后找到vi的一个邻接顶点的一个邻接顶点vi1 ；：从：从vi1出发，深度优先搜索访问和出发，深度优先搜索访问和vi1相邻接且未被访问的所有顶相邻接且未被访问的所有顶点；点；：转：转 ，直到和，直到和vi相邻接的所有顶点都被访问为止相邻接的所有顶点都被访问为止 ：继续选取图中未被访问顶点：继续选取图中未被访问顶点vj作为起始顶点，转作为起始顶点，转(1)，直到图中，直到图中所有顶点都被访问为止。所有顶点都被访问为止。例如对右边的这个无向图深度优先遍历，假定先从1出发程序以如下顺序遍历：125，然后退回

28、到2，退回到1。从1开始再访问未被访问过的点3，3没有未访问的邻接点，退回1。再从1开始访问未被访问过的点4，再退回1。起点1的所有邻接点都已访问，遍历结束。12345下面给出的深度优先遍历的参考程序，假设图以邻接表存储voiddfs(inti)/图用数组模拟邻接表存储，访问点ivisitedi=true;/标记为已经访问过for(intj=1;j=numi;j+)/遍历与i相关联的所有未访问过的顶点if(!visitedgij)dfs(gij);主程序如下:intmain()memset(visited,false,sizeof(visited);for(inti=1;i=n;i+)/每一个

29、点都作为起点尝试访问，因为不是从任何/一点开始都能遍历整个图的，例如下面的两个图。if(!visitedi)dfs(i);return0;12345以3为起点根本不能遍历整个图这个非连通无向图任何一个点为起点都不能遍历整个图14523广度优先搜索BFS广度优先搜索(Breadth First Search-BFS)遍历类似树的按层次遍历的过程。1 算法思想 设初始状态时图中的所有顶点未被访问，则： ：从图中某个顶点vi出发，访问vi；：访问vi的所有相邻接且未被访问的所有顶点vi1，vi2，vim；：以vi1，vi2， ，vim的次序，以vij(1jm)依此作为vi ，转； ：继续选取图中未被

30、访问顶点vk作为起始顶点，转，直到图中所有顶点都被访问为止。下图是有向图的广度优先搜索遍历示例(浅色箭头)。上述图的BFS次序是：v1 v2 v4 v3 v5(b) G的正邻接链表的正邻接链表13 014 2 3 01234MAX_VEX-1v1 2 v2 0 v3 3v4 1 v5 1 有向图广度优先搜索遍历有向图广度优先搜索遍历(a) 有向图有向图Gv1v2v3v4v5 用广度优先搜索算法遍历图与深度优先搜索算法遍历图的唯一区别是邻接点搜索次序不同，因此，广度优先搜索算法遍历图的总时间复杂度为O(n+e) 。 图的遍历可以系统地访问图中的每个顶点，因此，图的遍历算法是图的最基本、最重要的算

31、法，许多有关图的操作都是在图的遍历基础之上加以变化来实现的。【例题】无向图的BFS【问题描述】一个无向图，从指定顶点出发进行BFS，求遍历得到的顶点序。【文件输入】第1行：2个空格分开的整数n(2=n=200)和m(10=m=20000)，分别表示图的顶点数和边数。第2.m+1行：每行2个空格分开的整数i，j，i表示一条边的起点，j表示终点。第m2行：1个整数k(1=k=n),表示指定的顶点。【文件输出】只一行顶点序。要求在同一层上，顶点序号从小到大输出。#includeusing namespace std;int a101101,f101,q101,n,m,i,st;void init()

32、 int i,j,x,y; cinnm; memset(f,0,sizeof(f); for(i=1;ixy;axy=1;ayx=1; cinst;void dfs(int i)/深搜DFS int j; couti ;fi=1; for(j=1;j=n;j+)if(fj=0)&(aij=1)dfs(j);void bfs(int i)/广搜BFS int j,k,open,closed; memset(q,0,sizeof(q); open=0;closed=1;q1=i;/i进队列 couti ; fi=1; /标志 while(openclosed) /队列不空 open+;k=qope

33、n; /出队 for(j=1;j=n;j+) if(akj=1)&(fj=0) coutj ; fj=1;closed+;qclosed=j; int main() init(); /dfs(st);coutendl;memset(f,0,sizeof(f); bfs(st);二、欧拉图 1、欧拉路： 欧拉路径：图G中每条边经过一次且仅一次的路径称作欧拉路径。如下图中存在一条从顶点1到顶点6的欧拉路。一笔画问题其实本质上就是判断一个图是否存在欧拉路。无向图欧拉路存在的充要条件：图是连通的；图中有且仅有0个或2个度数为奇数的点。若存在2个奇点，则欧拉路一定是从一个奇点出发，以另一个奇点结束。 2

34、、欧拉回路：图G中每条边经过一次且仅一次的回路称作欧拉回路。著名的柯尼斯堡七桥问题(图论起源),本质上就是讨论一个图的欧拉回路问题。 一个无向图有欧拉回路的必要条件是：一个无向图有欧拉回路的必要条件是：图是连通的；图中所有点的度均为偶数。图是连通的；图中所有点的度均为偶数。 求欧拉路的算法很简单，使用深度优先遍历即可。 根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行DFS，时间复杂度为O(m+n)，m为边数，n是点数。 以下是寻找一个图的欧拉路的算法实现： 样例输入:第一行n，m，有n个点，m条边，以下m行描述每条边连接的两点。 55 12 2

35、3 34 45 51 样例输出:欧拉路或欧拉回路 154321【参考程序】Euler.cpp#include#includeusing namespace std;#define maxn 101int gmaxnmaxn; /此图用邻接矩阵存储int dumaxn; /记录每个点的度，就是相连的边的数目int circuitmaxn; /用来记录找到的欧拉路的路径int n,e,circuitpos,i,j,x,y,start;void find_circuit(int i) /这个点深度优先遍历过程寻找欧拉路 int j; for (j = 1; j n e; for (i = 1; i

36、x y; gyx = gxy = 1; dux+; /统计每个点的度 duy+; start = 1; /如果有奇点，就从奇点开始寻找，这样找到的就是 for (i = 1; i = n; i+) /欧拉路。没有奇点就从任意点开始， if (dui%2 = 1) /这样找到的就是欧拉回路。(因为每一个点都是偶点) start = i; circuitpos = 0; find_circuit(start); for (i = 1; i = circuitpos; i+) cout circuiti ; cout endl; return 0; 注意以上程序具有一定的局限性，对于下面这种情况它不

37、能很好地处理： 上图具有多个欧拉回路，而本程序只能找到一个回路。读者在遇到具体问题时，还应对程序作出相应的修改。 三、哈密尔顿环 欧拉回路是指不重复地走过所有路径的回路，而哈密尔顿环是指不重复地走过所有的点，并且最后还能回到起点的回路。 哈密顿通路（回路）与哈密顿图（Hamilton图）通过图G的每个结点一次，且仅一次的通路（回路），就是哈密顿通路（回路）.存在哈密顿回路的图就是哈密顿图 美国图论数学家奥勒在1960年给出了一个图是哈密尔顿图的充分条件：对于顶点个数大于2的图，如果图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密顿图。闭合的哈密顿路径称作哈密顿圈，含有图中所有顶点的路径

38、称作哈密顿路径。 【例题1】哈密顿路问题【问题描述】邮递员在送信时，为了节省路途，自己规定：每次总是从n个村子中选择其中一个合适的村子出发，途经每个村子仅且经过一次，送完所有的信。 已知各个村子的道路连通情况。请你帮邮递员选择一条合适的路线。【文件输入】第1行：整数n(2=n=200)：村子的个数。接下来是一个n*n的0、1矩阵（每2个数之间有1个空格），表示n个村子的连通情况，如：ai,j=1 ，表示第i和第j个村子之间有路可走，如果ai,j=0，表示他们之间无路可走。 【文件输出】只有一行为1个整数表示可行的方案总数。 #include#include using namespace st

39、d;int a201201,visit201,found,n,sum;void init() int i,j; scanf(%d,&n); for(i=1;i=n;i+) for(j=1;j=n;j+)scanf(%d,&aij);void dfs(int i,int k) int j; if(k=n)found=1;sum+;return; for(j=1;j=n;j+) if(aij=1)&(visitj=0) visitj=1; dfs(j,k+1); visitj=0; intmain()inti;init();found=0;sum=0;for(i=1;i=n;i+)memset(v

40、isit,0,sizeof(visit);visiti=1;dfs(i,1);if(found=0)printf(%d,0);elseprintf(%d,sum);return0;使用简单的深度优先搜索，就能求出一张图中所有的哈密尔顿环。下面给出一段参考程序： #include #include usingnamespacestd; intstart,length,x,n; boolvisited101,v1101; intans101,num101; intg101101; voidprint() inti; for(i=1;i=length;i+) cout“”ansi; coutendl

41、; void dfs(int last,int i) void dfs(int last,int i) /图用数组模拟邻接表存储，访问点图用数组模拟邻接表存储，访问点i i，lastlast表表示上次访问的点示上次访问的点 visitedi = true; visitedi = true; / /标记为已经访问过标记为已经访问过 v1i = true; v1i = true; / /标记为已在一张图中出现过标记为已在一张图中出现过 ans+length = i; ans+length = i; / /记录下答案记录下答案 for (int j = 1; j = numi; j+) for (int j = 1; j = numi; j+) if (gij=x&gij!=last) if (gij=x&gij!=last) / /回到起点，构成哈密尔顿环回到起点，构成哈密尔顿环 ans+length = gij; ans+length = gij; print(); print(); / /这里说明找到了一个环，则输出这里说明找到了一个环，则输出ansans数组。数组。length-;length-;break;break; if (!visitedgij) dfs(i,gij); if (!visitedgij)