图及其应用一精品文稿.ppt

《图及其应用一精品文稿.ppt》由会员分享，可在线阅读，更多相关《图及其应用一精品文稿.ppt（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图及其应用一第1页，本讲稿共80页一、一、图的基本概念图的基本概念1、图的的定义、图的的定义 图是由顶点图是由顶点V V的集合和边的集合和边E E的集合组成的二元组：的集合组成的二元组：记记G=G=（V V，E E）第2页，本讲稿共80页2、无向图和有向图、无向图和有向图无向图：无向图：在图在图G=G=（V V，E E）中，如果对于任意的）中，如果对于任意的a a，bVbV，当，当(a(a，b)Eb)E时，必有（时，必有（b b，a a）E E（即关系（即关系R R对称），对称图为无向对称），对称图为无向图。图。在一无向图中用不带箭头的边连接两个有关联的顶点。在一无向图中用不带箭头的边连接两个

2、有关联的顶点。V=V1,V2,V3,V4,V5E=(V1,V2),(V2,V3),(V3,V4),(V4,V5),(V5,V1),(V2,V5),(V4,V1)第3页，本讲稿共80页有向图：有向图：如果对于任意的如果对于任意的a a，bVbV，当，当(a(a，b)Eb)E时时 ，(b(b，a)Ea)E未必成未必成立，则称此图为有向图。立，则称此图为有向图。在有向图中，通常用带箭头的边连接两个有关联的结点。在有向图中，通常用带箭头的边连接两个有关联的结点。V=V1,V2,V3,V4 V=V1,V2,V3,V4 E=,E=,第4页，本讲稿共80页顶点的度：顶点的度：无向图：与顶点关联的边的数目。无

3、向图：与顶点关联的边的数目。有向图：等于该顶点的入度与出度之和。有向图：等于该顶点的入度与出度之和。入度入度以该顶点为终点的边的数目和以该顶点为终点的边的数目和出度出度以该顶点为起点的边的数目和以该顶点为起点的边的数目和 度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。3 3、顶点的度、顶点的度第5页，本讲稿共80页 练习题练习题:1.1.假设我们用假设我们用d=(a1,a2,.,a5),d=(a1,a2,.,a5),表示无向图表示无向图G G的的5 5个顶点的度数，个顶点的度数，下面给出的哪（些）组下面给出的哪（些）组d d 值合理（值合理

4、（）。）。A A）55，4 4，4 4，3 3，1 B1 B）44，2 2，2 2，1 1，1 C1 C）33，3 3，3 3，2 2，22 D D）55，4 4，3 3，2 2，1 E1 E）22，2 2，2 2，2 2，222.2.无向图无向图G G有有1616条边，有条边，有3 3个个4 4度顶点、度顶点、4 4个个3 3度顶点，其余顶点的度度顶点，其余顶点的度均小于均小于3 3，则，则G G至少至少_个顶点。个顶点。第6页，本讲稿共80页4 4、路径和连通集路径和连通集 在在图图G=G=（V V，E E）中中，如如果果对对于于结结点点a a，b b，存存在在满满足足下下述述条条件的结点

5、序列件的结点序列x x1 1xxk k(k1)(k1)x x1 1=a=a，x xk k=b=b (x(xi i，x xi+1i+1)E i=1E i=1k-1k-1则则称称结结点点序序列列x x1 1=a=a，x x2 2，x xk k=b=b为为结结点点a a到到结结点点b b的的一一条条路路径径，而而路路径径上上边边的的数数目目k-1k-1（或或者者沿沿路路径径各各边边权权值值之之和和）称称为为该该路路径的长度，并称结点集合径的长度，并称结点集合xx1 1，x xk k 为连通集。为连通集。V1,v2,v5,v4第7页，本讲稿共80页5 5、简单路径和回路、简单路径和回路如如果果一一条条

6、路路径径上上的的结结点点除除起起点点x x1 1和和终终点点x xk k可可以以相相同同外外，其其它它结结点点均均不不相相同同，则则称称此此路路径径为为一一条条简简单单路路径径。图图(a)(a)中中v v1 1vv2 2vv3 3是是一一条条简简单单路路径径，v v1 1vv3 3vv4 4vv1 1vv3 3不不是简单路径。是简单路径。x x1 1=x=xk k的的简简单单路路径径称称为为回回路路（也也称称为为环环）。例例如如图图(b)(b)中中，v v1 1vv2 2vv1 1为一条回路。为一条回路。第8页，本讲稿共80页例157324G26例245136G1路径：1，2，3，5，6，3路

7、径长度：5简单路径：1，2，3，5回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，3，1第9页，本讲稿共80页二、图的存储结构（教材二、图的存储结构（教材P79P79）图的邻接矩阵表示法图的邻接矩阵表示法 邻邻接接矩矩阵阵是是表表示示结结点点间间相相邻邻关关系系的的矩矩阵阵。若若G=G=（V V，E E）是是一一个个具具有有n n个个结结点点的的图图，则则G G的邻接矩阵是如下定义的二维数组的邻接矩阵是如下定义的二维数组a a，其规模为，其规模为n*nn*n 1(1(或权值或权值)表示表示 顶点顶点i i和顶点和顶点j j有边有边(

8、i(i和和j j的路程的路程)Aij=Aij=0 0（或（或）表示顶点表示顶点i i和顶点和顶点j j无边无边 二维数组的行、列号表示顶点编号第10页，本讲稿共80页上图中的图上图中的图G G1 1和图和图G G2 2对应的相邻矩阵分别为：对应的相邻矩阵分别为：无向带权图的邻接(代价)矩阵表示有向无权图的邻接矩阵表示第11页，本讲稿共80页邻接矩阵的特点：邻接矩阵的特点：1)1)无向图的邻接矩阵是对称的，而有向图则不是。无向图的邻接矩阵是对称的，而有向图则不是。2)2)邻接矩阵方便度数的计算。用邻接矩阵表示图邻接矩阵方便度数的计算。用邻接矩阵表示图:(1)(1)容易判定任意两个结点之间是否有边

9、相联容易判定任意两个结点之间是否有边相联;(2)(2)容易求得各个结点的度数。容易求得各个结点的度数。对于无权无向图的邻接矩阵，第对于无权无向图的邻接矩阵，第i i行元素值的和就是行元素值的和就是ViVi的度的度数；数；对于无权有向图的邻接矩阵，第对于无权有向图的邻接矩阵，第i i行元素值的和就是行元素值的和就是ViVi的出的出度，第度，第i i列元素值的和就是列元素值的和就是ViVi的入度；的入度；对于有权无向图的邻接矩阵，第对于有权无向图的邻接矩阵，第i i行（或第行（或第i i列）中元素值列）中元素值00的元素个数就是的元素个数就是ViVi的度数；的度数；对于有权有向图的邻接矩阵，第对于

10、有权有向图的邻接矩阵，第i i行中元素值行中元素值00的元素个的元素个数就是数就是ViVi的出度；第的出度；第i i列元素值列元素值00的元素个数就是的元素个数就是ViVi的入度。的入度。第12页，本讲稿共80页例1452375318642各顶点的度是多少？0618360240120078400530750第13页，本讲稿共80页读入数据构造邻接矩阵（P80）n n竞赛题中一般图的数据是以这种方式给出的：竞赛题中一般图的数据是以这种方式给出的：n n题中会指定顶点数的最大值，以便于定义一个全局二维数组作题中会指定顶点数的最大值，以便于定义一个全局二维数组作为邻接矩阵为邻接矩阵n n数据文件的第

11、数据文件的第1 1行一般是图的顶点个数行一般是图的顶点个数N N以及边数以及边数MMn n接下来一般有接下来一般有MM行，每行有行，每行有2 2个或个或3 3个整数，描述了每条边的信个整数，描述了每条边的信息：息：如果是如果是2 2个整数个整数i i，j j，则一般表示顶点，则一般表示顶点i i和顶点和顶点j j有一条边相连有一条边相连 如果是如果是3 3个整数个整数i i，j j，k k，则一般表示顶点，则一般表示顶点i i和顶点和顶点j j相连的权值为相连的权值为k kn n针对图数据的这种结构，我们会用如下的代码来构造邻接矩针对图数据的这种结构，我们会用如下的代码来构造邻接矩阵：阵：第1

12、4页，本讲稿共80页const int MAXN=201;/const int MAXN=201;/最大顶点数最大顶点数int aMAXNMAXN,n,m,i,j,k,x;int aMAXNMAXN,n,m,i,j,k,x;scanf(%d%d,&n,&m);scanf(%d%d,&n,&m);for(i=1;i=m;i+)/for(i=1;i=m;i+)/读入读入mm条边条边scanf(%d%d,&j,&k);scanf(%d%d,&j,&k);ajk=1;/ajk=1;/若是有向图，则只赋值若是有向图，则只赋值ajkajkakj=1;/akj=1;/若是无向图，则一定要赋值若是无向图，则一

13、定要赋值akjakj 如果是构造带权图，则上述如果是构造带权图，则上述for for 语句中的代码改为：语句中的代码改为：scanf(%d%d,&j,&k,&x);scanf(%d%d,&j,&k,&x);ajk=x;/ajk=x;/若是有向图，则只赋值若是有向图，则只赋值ajkajkakjl=x;/akjl=x;/若是无向图，则一定要赋值若是无向图，则一定要赋值akjakj第15页，本讲稿共80页邻接矩阵主对角线元素的处理n n在竞赛中很少有图数据是顶点带自环边的，因此邻接矩阵的主在竞赛中很少有图数据是顶点带自环边的，因此邻接矩阵的主对角线元素对角线元素aii(1=i=n)aii(1=i=n

14、)一般都是一般都是0 0。n n在前面讲的邻接矩阵的构造方法中，如果顶点在前面讲的邻接矩阵的构造方法中，如果顶点i i，j j之间没有边，则之间没有边，则aijaij也表示为也表示为0 0。在大多数图的算法中，不区别这两种值。在大多数图的算法中，不区别这两种值为为0 0的情况是可以的。的情况是可以的。n n而在某些图算法中，必须要区别主对角线元素和其它非主对角线元素，而在某些图算法中，必须要区别主对角线元素和其它非主对角线元素，这时就用另外的特殊值来表示无边相连的情况。特殊值一般取一个很这时就用另外的特殊值来表示无边相连的情况。特殊值一般取一个很大的正数（或负数），实现实现代码如下：大的正数（

15、或负数），实现实现代码如下：第16页，本讲稿共80页const int BIG=99999999;/const int BIG=99999999;/表示无穷大表示无穷大for(i=1;i=n;i+)/for(i=1;i=n;i+)/初始化初始化 for(j=1;j=n;j+)for(j=1;j=n;j+)aij=BIG;aij=BIG;aii=0;aii=0;for(i=1;i=m;i+)/for(i=1;i=m;i+)/读入边数据读入边数据scanf(%d%d%d,&j,&k,&x);scanf(%d%d%d,&j,&k,&x);ajk=x;ajk=x;akj=x;/akj=x;/这句无向图

16、才要这句无向图才要 邻接矩阵的优缺点见教材邻接矩阵的优缺点见教材P80P80判断判断i i，j j有无边相连：有无边相连：O(1)O(1)找找i i的邻接点，计算入度、出度：的邻接点，计算入度、出度：O(n)O(n)空间复杂性高：空间复杂性高：O(n2)O(n2)第17页，本讲稿共80页边集数组表示法（教材P80）n n一个一维数组存储图一个一维数组存储图n n每个元素表示一条边：起点、终点、权值（如果有的话）每个元素表示一条边：起点、终点、权值（如果有的话）n n适用于：对边进行依次处理的算法，适合存储顶点多但边很少适用于：对边进行依次处理的算法，适合存储顶点多但边很少的稀疏图的稀疏图n n

17、缺点：缺点：判断判断i i，j j有无边相连：有无边相连：O(E)O(E)找找i i的邻接点，计算入度、出度：的邻接点，计算入度、出度：O(E)O(E)n n优点：结构简单优点：结构简单第18页，本讲稿共80页边集数组表示法的实现const int MAXEDGE=2000;const int MAXEDGE=2000;struct node struct node int s,t;/int s,t;/边的起点和终点边的起点和终点int w;/int w;/边的权值边的权值 node edgeMAXEDGE;node edgeMAXEDGE;int n,m,i,j,k,x;int n,m,i,

18、j,k,x;scanf(%d%d,&n,&m);scanf(%d%d,&n,&m);for(i=1;i=m;i+)for(i=1;i=m;i+)scanf(%d%d%d,&j,&k,&x);scanf(%d%d%d,&j,&k,&x);edgei.s=j;edgei.s=j;edgei.t=k;edgei.t=k;edgei.w=x;edgei.w=x;第19页，本讲稿共80页邻接表表示法（P81）n n邻接表表示法是指对图中的每个顶点邻接表表示法是指对图中的每个顶点Vi(1=i=n)Vi(1=i=n)建立一个邻接关系的单链表，建立一个邻接关系的单链表，并把它们的表头指针用一维数组存储起来的一

19、种表示方法。并把它们的表头指针用一维数组存储起来的一种表示方法。n n为每个顶点为每个顶点ViVi建立的单链表，是表示以该顶点为建立的单链表，是表示以该顶点为起点起点的所有边的信息。以下图的所有边的信息。以下图（教材图（教材图5 52 2）为例，顶点）为例，顶点v1v1与与v2v2、v3v3、v5v5相邻，因此在相邻，因此在v1v1的单链表里就包的单链表里就包含含3 3条边的信息。条边的信息。v1v2v3v4v5524101183253853顶点v1的单链表有3个结点，表示有3条边与v1相接，有3个顶点（v2、v3、v5）是v1的邻接点不表示v2与v3相邻，v3与v5相邻第20页，本讲稿共80

20、页邻接表表示法（P81）n n一维指针数组存储了每个顶点的单链表的头指针。一般就用数组下标表示了一维指针数组存储了每个顶点的单链表的头指针。一般就用数组下标表示了起点编号。例如起点编号。例如v1v1单链表的头指针就存储在单链表的头指针就存储在adj1adj1中。中。n n下图的完整邻接表如下所示：下图的完整邻接表如下所示：v1v2v3v4v552410118325385315325618225431051113265114103412345第21页，本讲稿共80页邻接表的数据结构const int MAXV=201;/const int MAXV=201;/最大顶点数最大顶点数struct n

21、ode struct node int v;/int v;/邻接点序号邻接点序号 int wt;/int wt;/权值，如果是带权图的话权值，如果是带权图的话 node*next;/node*next;/邻接单链表指针邻接单链表指针;node*adjMAXV;/node*adjMAXV;/每个顶点建一个单链表构造邻接表每个顶点建一个单链表构造邻接表int n,m;/nint n,m;/n表示读入的顶点个数，表示读入的顶点个数，mm表示读入的边条数表示读入的边条数第22页，本讲稿共80页创建邻接表void createlist()/void createlist()/创建邻接表创建邻接表 int

22、 i,j,k,x;int i,j,k,x;node*p;node*p;scanf(%d%d,&n,&m);/scanf(%d%d,&n,&m);/读入顶点数和边数读入顶点数和边数 for(i=1;i=n;i+)/for(i=1;i=n;i+)/初始化每个顶点的边表为初始化每个顶点的边表为NULLNULL adji=NULL;adji=NULL;for(i=1;i=m;i+)for(i=1;iv=k;/jp-v=k;/j的邻接点是的邻接点是k k p-wt=x;/p-wt=x;/边的权值是边的权值是x x p-next=adjj;/p-next=adjj;/新节点插在顶点新节点插在顶点j j的边

23、表的表头位置的边表的表头位置 adjj=p;adjj=p;/以下是无向图需要构造的对称边以下是无向图需要构造的对称边 p=new node;p=new node;p-v=j;/k p-v=j;/k的邻接点是的邻接点是j j p-wt=x;p-wt=x;p-next=adjk;/p-next=adjk;/新节点插在顶点新节点插在顶点k k的边表的表头位置的边表的表头位置 adjk=p;adjk=p;第23页，本讲稿共80页邻接表的优缺点（P82）n n便于查找后继顶点、以该点为起点的边、出度。便于查找后继顶点、以该点为起点的边、出度。n n不便于查找前趋顶点、以该点为终点的边、入度。解决办法：不

24、便于查找前趋顶点、以该点为终点的边、入度。解决办法：建立逆邻接表，即把以某顶点为终点的顶点放在一个单链表中。建立逆邻接表，即把以某顶点为终点的顶点放在一个单链表中。n n和邻接矩阵相比，构造邻接表的编程复杂性要高一些，但是查找后继和邻接矩阵相比，构造邻接表的编程复杂性要高一些，但是查找后继顶点的效率要高顶点的效率要高O(e/n)vs.O(n)O(e/n)vs.O(n)。如果边比较稀疏，显然用邻。如果边比较稀疏，显然用邻接表存储图比较好。接表存储图比较好。第24页，本讲稿共80页编程练习n n求一个有向图中指定顶点的出度。求一个有向图中指定顶点的出度。n n输入数据：第输入数据：第1 1行：行：

25、2 2个空格分开的整数个空格分开的整数n(2=n=200)n(2=n=200)和和m(10=m=20000)m(10=m=20000)，分别表示图的顶点数和边数。，分别表示图的顶点数和边数。n n第第2.m+12.m+1行：每行行：每行2 2个空格分开的整数个空格分开的整数i i，j j，i i表示一条边的起点，表示一条边的起点，j j表示终点。表示终点。n n第第mm2 2行：行：1 1个整数个整数k(2=k=n),k(2=k=n),表示指定的顶点。表示指定的顶点。n n输出数据：第输出数据：第1 1行：行：1 1个整数个整数odod，表示顶点，表示顶点k k的出度。的出度。n n要求：分别

26、用邻接矩阵和邻接表存储图。要求：分别用邻接矩阵和邻接表存储图。第25页，本讲稿共80页三、图的遍历三、图的遍历给出一个图给出一个图G G和其中任意一个结点和其中任意一个结点V V，从，从V V出发访问出发访问G G中所有结中所有结点，每一个结点被访问一次（不是只经过一次），这就叫图点，每一个结点被访问一次（不是只经过一次），这就叫图的遍历。的遍历。通常有两种遍历方法：通常有两种遍历方法：深度优先搜索深度优先搜索dfsdfs 广度优先搜索广度优先搜索bfsbfs 第26页，本讲稿共80页1 1、深度优先搜索、深度优先搜索DFSDFS方法：从图的某一顶点V1出发，访问此顶点；然后依次从V1的未被访

27、问的邻接点出发，深度优先遍历图，直至图中所有和V1相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。为了避免重复访问某个顶点，设一个标志数组visit，顶点i未访问时，visiti的值为false，访问后就改为true。V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V5 V3 V6 V7可以从任一顶点出发进行DFS第27页，本讲稿共80页V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍历：V1 V2 V4 V8 V5 V6 V3 V7深度遍历：V1 V2 V4 V8

28、V5 V6 V3 V7第28页，本讲稿共80页V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V3 V6 V7 V5第29页，本讲稿共80页在程序中实现深度优先搜索n n算法算法:从图的某一顶点从图的某一顶点V1V1出发，访问此顶点；然后出发，访问此顶点；然后依次从依次从V1V1的未被访问的邻接点出发，深度优先遍历图，的未被访问的邻接点出发，深度优先遍历图，直至图中所有和直至图中所有和V1V1相通的顶点都被访问到。相通的顶点都被访问到。n n如何判别如何判别V V的邻接点是否被访问？的邻接点是否被访问？n n解决的办法是解决的办法是:为每个顶点设立一个为每个顶点设立一个“访

29、问标志访问标志 visiti”visiti”n n如果图不连通，则一次如果图不连通，则一次DFSDFS只能访问所有与只能访问所有与V1V1连通的连通的顶点。要对整个图进行遍历，则需要再任找一个尚未顶点。要对整个图进行遍历，则需要再任找一个尚未访问的顶点，再次访问的顶点，再次DFSDFS，直到所有顶点均被访问为止。，直到所有顶点均被访问为止。第30页，本讲稿共80页abchdekfg812345670F F F F F F F F F0 1 2 3 4 5 6 7 8TTTTTTTTTachdkfebgachkfedbg访问标志访问标志:访问次序访问次序:例如例如:achdkfe第31页，本讲稿

30、共80页参考代码/从顶点从顶点i i出发进行深度优先搜索出发进行深度优先搜索,邻接表实现邻接表实现/适用于有向图和无向图适用于有向图和无向图void dfs(int i)void dfs(int i)node*p;node*p;cout i;/cout v=false)/if(visitp-v=false)/如果邻接点未访问如果邻接点未访问 dfs(p-v);/dfs(p-v);/则对其递归则对其递归DFSDFS p=p-next;/p=p-next;/取下一个邻接点取下一个邻接点 第32页，本讲稿共80页参考代码void dfstravel()/void dfstravel()/对图进行深度

31、优先遍历对图进行深度优先遍历 int i;int i;memset(visit,0,sizeof(visit);/memset(visit,0,sizeof(visit);/清访问标志清访问标志 for(i=1;i=n;i+)for(i=1;i=n;i+)if(!visiti)if(!visiti)dfs(i);dfs(i);第33页，本讲稿共80页DFS的应用1 1、犯罪团伙、犯罪团伙 警察抓到了警察抓到了n n个罪犯，警察根据经验知道他们属于不同的个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，

32、知道其中的一些罪犯之间相互认识，已知同一犯罪团伙的成员之道其中的一些罪犯之间相互认识，已知同一犯罪团伙的成员之间直接或间接认识。有可能一个犯罪团伙只有一个人。请你根间直接或间接认识。有可能一个犯罪团伙只有一个人。请你根据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编号从号从1 1至至n n。输入：输入：第一行：第一行：n n（=5000,=5000,罪犯数量），罪犯数量），m m（5000050000，关系数量），关系数量）以下以下m m行：每行两个数：行：每行两个数：i i 和和j j，中间一个空格隔开，表示罪犯，中间一个空格隔开，

33、表示罪犯i i和罪犯和罪犯j j相互认识。相互认识。输出：输出：一个整数，犯罪团伙的数量。一个整数，犯罪团伙的数量。第34页，本讲稿共80页样例输入：11 8 1 24 35 41 35 67 105 108 9输出：3说明：共三个犯罪团伙。第35页，本讲稿共80页分析n n把人处理成顶点，把认识关系处理成边，犯罪团伙构成一个图（有向还是无向？）则把人处理成顶点，把认识关系处理成边，犯罪团伙构成一个图（有向还是无向？）则根据输入数据可以构造一个邻接表（可以用邻接矩阵吗？如果不能请说明原因）。根据输入数据可以构造一个邻接表（可以用邻接矩阵吗？如果不能请说明原因）。n n从从1 1到到n n枚举顶

34、点枚举顶点ViVi，从，从ViVi进行进行DFSDFS，则能找到一个团伙。然后再另选一个未访，则能找到一个团伙。然后再另选一个未访问的顶点，再次问的顶点，再次DFSDFS，直到所有顶点均被访问。最后，调用，直到所有顶点均被访问。最后，调用DFSDFS的次数就的次数就是团伙的个数。是团伙的个数。第36页，本讲稿共80页const maxn=1000;var a:array1.maxn,1.maxnof longint;visited:array1.maxnof 0.1;t:array1.maxnof char;n,m,i,s:longint;procedure init;var i,x,y:lo

35、ngint;begin assign(input,group5.in);reset(input);readln(n);readln(m);for i:=1 to m do begin readln(x,y);ax,y:=1;ay,x:=1;end;close(input);end;procedure dfs(i:longint);var j:longint;begin visitedi:=1;for j:=1 to n do if(ai,j=1)and(visitedj=0)then dfs(j);end;Begin init;s:=0;for i:=1 to n do visitedi:=0

36、;for i:=1 to n do if visitedi=0 then begin dfs(i);inc(s);end;writeln(s);end.第37页，本讲稿共80页12354672 2、哈密顿路、哈密顿路 邮递员在送信时，为了节省路途，自己规定：每次总是从n个村子中选择其中一个合适的村子出发，途经每个村子仅且经过一次，送完所有的信。已知各个村子的道路连通情况。请你帮邮递员选择一条合适的路线。输入：第一行：整数n(2=n=200)：村子的个数。接下来是一个n*n的0、1矩阵，表示n个村子的连同情况，如：ai,j=1，表示第i和第j个村子之间有路可走，如果ai,j=0，表示他们之间无路

37、可走。输出：一条可行的路线输入：输入：70 1 0 1 1 0 01 0 1 0 1 0 00 1 0 0 0 0 11 0 0 0 0 0 01 1 0 0 0 1 00 0 0 0 1 0 10 0 1 0 0 1 0输出：输出：2 3 7 6 5 1 42 3 7 6 5 1 4第38页，本讲稿共80页分析分析n n题目的限制条件：题目的限制条件：“途经每个村子仅且经过一次途经每个村子仅且经过一次”，表明在深搜的过，表明在深搜的过程中，程中，ViVi的邻接点中必须要有至少一个顶点是没有被访问过的。的邻接点中必须要有至少一个顶点是没有被访问过的。这样才能沿着该点继续这样才能沿着该点继续DF

38、SDFS下去。下去。n n如果恰能遍历全部结点，则找到一条路径，输出这条路径即可。如果恰能遍历全部结点，则找到一条路径，输出这条路径即可。怎样在怎样在DFSDFS的过程中保存路径？的过程中保存路径？n n如果在如果在DFSDFS的某一层出现了所有邻接点都被访问过了，则说明在的某一层出现了所有邻接点都被访问过了，则说明在上一层（以及更上层）的路由选择不正确，这时就要回溯到上层，上一层（以及更上层）的路由选择不正确，这时就要回溯到上层，换一个未被访问的结点换一个未被访问的结点,再次进行再次进行DFSDFS，看能否走通。，看能否走通。n n在换结点的时候，一定要清除前一个结点被访问过的标志信息，在换

39、结点的时候，一定要清除前一个结点被访问过的标志信息，这就是所谓的这就是所谓的“清理现场清理现场”的工作。如果不做这个操作，则求解的工作。如果不做这个操作，则求解几乎没有可能得到正确结果。几乎没有可能得到正确结果。第39页，本讲稿共80页const maxn=100;算法一var a:array1.maxn,1.maxnof integer;visited:array1.maxnof 0.1;b:array1.maxn of 1.maxn;n,m,i:integer;found:integer;procedure init;var i,j:integer;begin assign(input,a

40、.in);reset(input);readln(n);for i:=1 to n do for j:=1 to n do read(ai,j);close(input);end;procedure print;var i:integer;begin found:=1;for i:=1 to n-1 do write(bi,);writeln(bn);end;procedure dfs(i:integer);var j,k:integer;begin /m是当前访问的结点个数 if m=n then begin print;exit;end;for j:=1 to n do if(aj,i=1

41、)and(visitedj=0)then begin visitedj:=1;m:=m+1;bm:=j;dfs(j);visitedj:=0;m:=m-1;end;end;第40页，本讲稿共80页 Begin init;found:=0;for i:=1 to n do begin fillchar(visited,sizeof(visited),0);m:=1;b1:=i;visitedi:=1;dfs(i);end;if found=0 then writeln(no road);end.第41页，本讲稿共80页算法二算法二procedure dfs(i,k:integer);结点结点i是

42、路上的第是路上的第k个结点个结点 var j:integer;begin if k=n then print;for j:=1 to n do if(aj,i=1)and(visitedj=0)then begin visitedj:=1;bk+1:=j;dfs(j,k+1);visitedj:=0;end;end;Begin init;found:=0;for i:=1 to n do begin fillchar(visited,sizeof(visited),0);m:=1;b1:=i;visitedi:=1;dfs(i,1);end;if found=0 then writeln(no

43、 road);end.第42页，本讲稿共80页3 3、安排座位、安排座位 n n个个客客人人围围着着一一个个桌桌子子吃吃饭饭，每每一一个个人人都都至至少少认认识识其其他他的的2 2个个客客人人。请请设设计计程程序序求求得得n n个个人人的的一一种种坐坐法法，使使得得每每个个人人都都认认识他左右的客人。识他左右的客人。输入输入:第一行第一行:n:n（吃饭人的个数）。（吃饭人的个数）。以下以下n n行：第行：第i i行的第一个数行的第一个数k k表示第表示第i i个人认识的人数，后面个人认识的人数，后面k k个数依次为个数依次为i i认识的人的编号。认识的人的编号。输出：所有座法，要求第一个人为输

44、出：所有座法，要求第一个人为1 1号作为起点，按顺时针输号作为起点，按顺时针输出其它人的编号。出其它人的编号。样例输入：62 3 63 4 5 63 1 4 63 2 3 53 2 4 64 1 2 3 5样例输出：1 3 4 2 5 61 3 4 5 2 61 6 2 5 4 31 6 5 2 4 3第43页，本讲稿共80页分析分析:如如果果A A认认识识B,BB,B又又认认识识C,C,则则B B认认识识他他左左右右的的两两个个人人.继继续续这这个个过过程程,如如果果C C又又认认识识D,D,则则C C认认识识他他左左右右的的两两个个人人;这这其其实实就就是一个是一个DFSDFS过程过程.如

45、如果果最最后后一一个个人人能能认认识识第第一一个个人人,则则最最后后一一个个人人也也认认识识他他左左右右的两个人的两个人.这样就找到一组满足要求的解了这样就找到一组满足要求的解了.本题是求一个本题是求一个N N个顶点的简单回路问题个顶点的简单回路问题.第44页，本讲稿共80页procedure dfs(i:integer);var j,k:integer;begin if(n=m)and(ab1,bm=1)then print;for j:=1 to n do if(ai,j=1)and(visitedj=0)then begin visitedj:=1;m:=m+1;bm:=j;dfs(j)

46、;visitedj:=0;m:=m-1;end;end;Begin init;fillchar(visited,sizeof(visited),0);found:=0;m:=1;b1:=1;visited1:=1;dfs(1);if found=0 then writeln(no road);end.第45页，本讲稿共80页4、素数链设计程序将1,2,20排成一排，使任意两个相邻的数的和为素数。第1个和最后一个的和也为素数.输出:120个数的排列方式.第46页，本讲稿共80页const maxn=100;var visited:array1.maxnof 0.1;b:array1.maxn o

47、f 1.maxn;n,m,i:integer;found:integer;function check(i:integer):boolean;var j:integer;begin for j:=2 to i-1 do if i mod j=0 then begin check:=false;exit;end;check:=true;end;procedure print;var i:integer;begin found:=1;for i:=1 to n-1 do write(bi,);writeln(bn);halt;end;第47页，本讲稿共80页 procedure dfs(i:int

48、eger);var j,k:integer;begin if(m=n)and(check(b1+bm)then print;for j:=1 to n do if(visitedj=0)and (check(i+j)then begin visitedj:=1;m:=m+1;bm:=j;dfs(j);visitedj:=0;m:=m-1;end;end;Begin fillchar(visited,sizeof(visited),0);n:=20;found:=0;m:=1;b1:=1;visited1:=1;dfs(1);if found=0 then writeln(no road);en

49、d.第48页，本讲稿共80页2 2、广度（宽度）优先搜索、广度（宽度）优先搜索BFSBFS 广度优先搜索广度优先搜索按层次按层次遍历的过程，其搜索过程如下：遍历的过程，其搜索过程如下：方法：从图的某一顶点V1出发，访问此顶点后，依次访问V1的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V5 V6 V7 V8第49页，本讲稿共80页V1V2V4V5V3V7V

50、6V8例例V1V2V4V5V3V7V6V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8第50页，本讲稿共80页V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V6 V7 V8 V5第51页，本讲稿共80页在程序中实现BFSn n从图的某一顶点从图的某一顶点V1V1出发，访问此顶点后，依次访问出发，访问此顶点后，依次访问V1V1的各个未曾的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；图，直