图及其应用一.pptx

2、无向图和有向图、无向图和有向图无向图：在图在图G=G=（V V，E E）中，如果对于任意的）中，如果对于任意的a a，bVbV，当，当(a(a，b)Eb)E时，必有（时，必有（b b，a a）E E（即关系（即关系R R对称），对称图为无向对称），对称图为无向图。图。在一无向图中用不带箭头的边连接两个有关联的顶点。在一无向图中用不带箭头的边连接两个有关联的顶点。V=V1,V2,V3,V4,V5E=(V1,V2),(V2,V3),(V3,V4),(V4,V5),(V5,V1),(V2,V5),(V4,V1)第1页/共79页有向图：有向图：如果对于任意的如果对于任意的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=,第2页/共79页顶点的度：顶点的度：无向图：与顶点关联的边的数目。无向图：与顶点关联的边的数目。有向图：等于该顶点的入度与出度之和。有向图：等于该顶点的入度与出度之和。入度入度以该顶点为终点的边的数目和以该顶点为终点的边的数目和出度出度以该顶点为起点的边的数目和以该顶点为起点的边的数目和 度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。3 3、顶点的度、顶点的度第3页/共79页 练习题:1.假设我们用d=(a1,a2,.,a5),表示无向图G的5个顶点的度数，下面给出的哪（些）组d 值合理（）。A）5，4，4，3，1 B）4，2，2，1，1 C）3，3，3，2，2 D）5，4，3，2，1 E）2，2，2，2，22.无向图G有16条边，有3个4度顶点、4个3度顶点，其余顶点的度均小于3，则G至少_个顶点。第4页/共79页4 4、路径和连通集路径和连通集 在在图图G=G=（V V，E E）中中，如如果果对对于于结结点点a a，b b，存存在在满满足足下下述述条条件的结点序列件的结点序列x x1 1x xk 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第5页/共79页5 5、简单路径和回路、简单路径和回路如如果果一一条条路路径径上上的的结结点点除除起起点点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为一条回路。为一条回路。第6页/共79页例157324G26例245136G1路径：1，2，3，5，6，3路径长度：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第7页/共79页二、图的存储结构（教材二、图的存储结构（教材P79P79）图的邻接矩阵表示法图的邻接矩阵表示法 邻邻接接矩矩阵阵是是表表示示结结点点间间相相邻邻关关系系的的矩矩阵阵。若若G=G=（V V，E E）是是一一个个具具有有n n个个结结点点的的图图，则则G G的的邻邻接接矩矩阵阵是是如如下下定定义义的的二二维维数数组组a a，其其规规模模为为n*nn*n 1(1(或权值或权值)表示表示 顶点顶点i i和顶点和顶点j j有边有边(i(i和和j j的路程的路程)Aij=Aij=0 0（或（或）表示顶点表示顶点i i和顶点和顶点j j无边无边 二维数组的行、列号表示顶点编号第8页/共79页上图中的图上图中的图G G1 1和图和图G G2 2对应的相邻矩阵分别为：对应的相邻矩阵分别为：无向带权图的邻接(代价)矩阵表示有向无权图的邻接矩阵表示第9页/共79页邻接矩阵的特点：1)无向图的邻接矩阵是对称的，而有向图则不是。2)邻接矩阵方便度数的计算。用邻接矩阵表示图:(1)容易判定任意两个结点之间是否有边相联;(2)容易求得各个结点的度数。对于无权无向图的邻接矩阵，第i行元素值的和就是Vi的度数；对于无权有向图的邻接矩阵，第i行元素值的和就是Vi的出度，第i列元素值的和就是Vi的入度；对于有权无向图的邻接矩阵，第i行（或第i列）中元素值0的元素个数就是Vi的度数；对于有权有向图的邻接矩阵，第i行中元素值0的元素个数就是Vi的出度；第i列元素值0的元素个数就是Vi的入度。第10页/共79页例1452375318642各顶点的度是多少？0618360240120078400530750第11页/共79页读入数据构造邻接矩阵（P80）竞赛题中一般图的数据是以这种方式给出的：题中会指定顶点数的最大值，以便于定义一个全局二维数组作为邻接矩阵数据文件的第1行一般是图的顶点个数N以及边数M接下来一般有M行，每行有2个或3个整数，描述了每条边的信息：如果是2个整数i，j，则一般表示顶点i和顶点j有一条边相连如果是3个整数i，j，k，则一般表示顶点i和顶点j相连的权值为k针对图数据的这种结构，我们会用如下的代码来构造邻接矩阵：第12页/共79页const int MAXN=201;/最大顶点数int aMAXNMAXN,n,m,i,j,k,x;scanf(%d%d,&n,&m);for(i=1;i=m;i+)/读入m条边scanf(%d%d,&j,&k);ajk=1;/若是有向图，则只赋值ajkakj=1;/若是无向图，则一定要赋值akj如果是构造带权图，则上述for 语句中的代码改为：scanf(%d%d,&j,&k,&x);ajk=x;/若是有向图，则只赋值ajkakjl=x;/若是无向图，则一定要赋值akj第13页/共79页邻接矩阵主对角线元素的处理在竞赛中很少有图数据是顶点带自环边的，因此邻接矩阵的主对角线元素aii(1=i=n)一般都是0。在前面讲的邻接矩阵的构造方法中，如果顶点i，j之间没有边，则aij也表示为0。在大多数图的算法中，不区别这两种值为0的情况是可以的。而在某些图算法中，必须要区别主对角线元素和其它非主对角线元素，这时就用另外的特殊值来表示无边相连的情况。特殊值一般取一个很大的正数（或负数），实现实现代码如下：第14页/共79页const int BIG=99999999;/表示无穷大for(i=1;i=n;i+)/初始化 for(j=1;j=n;j+)aij=BIG;aii=0;for(i=1;i=m;i+)/读入边数据scanf(%d%d%d,&j,&k,&x);ajk=x;akj=x;/这句无向图才要 邻接矩阵的优缺点见教材P80判断i，j有无边相连：O(1)找i的邻接点，计算入度、出度：O(n)空间复杂性高：O(n2)第15页/共79页边集数组表示法（教材P80）一个一维数组存储图每个元素表示一条边：起点、终点、权值（如果有的话）适用于：对边进行依次处理的算法，适合存储顶点多但边很少的稀疏图缺点：判断i，j有无边相连：O(E)找i的邻接点，计算入度、出度：O(E)优点：结构简单第16页/共79页边集数组表示法的实现const int MAXEDGE=2000;struct node int s,t;/边的起点和终点int w;/边的权值node edgeMAXEDGE;int n,m,i,j,k,x;scanf(%d%d,&n,&m);for(i=1;i=m;i+)scanf(%d%d%d,&j,&k,&x);edgei.s=j;edgei.t=k;edgei.w=x;第17页/共79页邻接表表示法（P81）邻接表表示法是指对图中的每个顶点Vi(1=i=n)建立一个邻接关系的单链表，并把它们的表头指针用一维数组存储起来的一种表示方法。为每个顶点Vi建立的单链表，是表示以该顶点为起点的所有边的信息。以下图（教材图52）为例，顶点v1与v2、v3、v5相邻，因此在v1的单链表里就包含3条边的信息。v1v2v3v4v5524101183253853顶点v1的单链表有3个结点，表示有3条边与v1相接，有3个顶点（v2、v3、v5）是v1的邻接点不表示v2与v3相邻，v3与v5相邻第18页/共79页邻接表表示法（P81）一维指针数组存储了每个顶点的单链表的头指针。一般就用数组下标表示了起点编号。例如v1单链表的头指针就存储在adj1中。下图的完整邻接表如下所示：v1v2v3v4v552410118325385315325618225431051113265114103412345第19页/共79页邻接表的数据结构const int MAXV=201;/最大顶点数struct node int v;/邻接点序号 int wt;/权值，如果是带权图的话 node*next;/邻接单链表指针;node*adjMAXV;/每个顶点建一个单链表构造邻接表int n,m;/n表示读入的顶点个数，m表示读入的边条数第20页/共79页创建邻接表void createlist()/创建邻接表 int i,j,k,x;node*p;scanf(%d%d,&n,&m);/读入顶点数和边数 for(i=1;i=n;i+)/初始化每个顶点的边表为NULL adji=NULL;for(i=1;iv=k;/j的邻接点是k p-wt=x;/边的权值是x p-next=adj j;/新节点插在顶点j的边表的表头位置 adj j=p;/以下是无向图需要构造的对称边 p=new node;p-v=j;/k的邻接点是j p-wt=x;p-next=adjk;/新节点插在顶点k的边表的表头位置 adjk=p;第21页/共79页邻接表的优缺点（P82）便于查找后继顶点、以该点为起点的边、出度。不便于查找前趋顶点、以该点为终点的边、入度。解决办法：建立逆邻接表，即把以某顶点为终点的顶点放在一个单链表中。和邻接矩阵相比，构造邻接表的编程复杂性要高一些，但是查找后继顶点的效率要高O(e/n)vs.O(n)。如果边比较稀疏，显然用邻接表存储图比较好。第22页/共79页编程练习求一个有向图中指定顶点的出度。输入数据：第1行：2个空格分开的整数n(2=n=200)和m(10=m=20000)，分别表示图的顶点数和边数。第2.m+1行：每行2个空格分开的整数i，j，i表示一条边的起点，j表示终点。第m2行：1个整数k(2=k=n),表示指定的顶点。输出数据：第1行：1个整数od，表示顶点k的出度。要求：分别用邻接矩阵和邻接表存储图。第23页/共79页三、三、图的遍历图的遍历给出一个图给出一个图G G和其中任意一个结点和其中任意一个结点V V，从，从V V出发访问出发访问G G中所有结中所有结点，每一个结点被访问一次（不是只经过一次），这就叫图点，每一个结点被访问一次（不是只经过一次），这就叫图的遍历。的遍历。通常有两种遍历方法：通常有两种遍历方法：深度优先搜索深度优先搜索dfsdfs 广度优先搜索广度优先搜索bfsbfs 第24页/共79页1 1、深度优先搜索、深度优先搜索DFSDFS方法：从图的某一顶点V1出发，访问此顶点；然后依次从V1的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V1相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。为了避免重复访问某个顶点，设一个标志数组visit，顶点i未访问时，visiti的值为false，访问后就改为true。V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V5 V3 V6 V7可以从任一顶点出发进行DFS第25页/共79页V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍历：V1 V2 V4 V8 V5 V6 V3 V7深度遍历：V1 V2 V4 V8 V5 V6 V3 V7第26页/共79页V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V3 V6 V7 V5第27页/共79页在程序中实现深度优先搜索算法:从图的某一顶点V1出发，访问此顶点；然后依次从V1的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V1相通的顶点都被访问到。如何判别V的邻接点是否被访问？解决的办法是:为每个顶点设立一个“访问标志 visiti”如果图不连通，则一次DFS只能访问所有与V1连通的顶点。要对整个图进行遍历，则需要再任找一个尚未访问的顶点，再次DFS，直到所有顶点均被访问为止。第28页/共79页abchdekfg812345670FFFFFFFFF0 1 2 3 4 5 6 7 8T T T T T T T T Tach d kfe bgachkfedbg访问标志访问标志:访问次序访问次序:例如:achdkfe第29页/共79页参考代码/从顶点i出发进行深度优先搜索,邻接表实现/适用于有向图和无向图void dfs(int i)node*p;cout v=false)/如果邻接点未访问 dfs(p-v);/则对其递归DFS p=p-next;/取下一个邻接点 第30页/共79页参考代码void dfstravel()/对图进行深度优先遍历 int i;memset(visit,0,sizeof(visit);/清访问标志 for(i=1;i=n;i+)if(!visiti)dfs(i);第31页/共79页DFS的应用1 1、犯罪团伙、犯罪团伙 警察抓到了警察抓到了n n个罪犯，警察根据经验知道他们属于不同的个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知道其中的一些罪犯之间相互认识，已知同一犯罪团伙的成员之道其中的一些罪犯之间相互认识，已知同一犯罪团伙的成员之间直接或间接认识。有可能一个犯罪团伙只有一个人。请你根间直接或间接认识。有可能一个犯罪团伙只有一个人。请你根据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编号从号从1 1至至n n。输入：输入：第一行：第一行：n n（=5000,=5000,罪犯数量），罪犯数量），m m（5000050000，关系数量），关系数量）以下以下m m行：每行两个数：行：每行两个数：i i 和和j j，中间一个空格隔开，表示罪犯，中间一个空格隔开，表示罪犯i i和罪犯和罪犯j j相互认识。相互认识。输出：输出：一个整数，犯罪团伙的数量。一个整数，犯罪团伙的数量。第32页/共79页样例输入：11 8 1 24 35 41 35 67 105 108 9输出：3说明：共三个犯罪团伙。第33页/共79页分析把人处理成顶点，把认识关系处理成边，犯罪团伙构成一个图（有向还是无向？）则根据输入数据可以构造一个邻接表（可以用邻接矩阵吗？如果不能请说明原因）。从1到n枚举顶点Vi，从Vi进行DFS，则能找到一个团伙。然后再另选一个未访问的顶点，再次DFS，直到所有顶点均被访问。最后，调用DFS的次数就是团伙的个数。第34页/共79页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:longint;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;for i:=1 to n do if visitedi=0 then begin dfs(i);inc(s);end;writeln(s);end.第35页/共79页12354672 2、哈密顿路、哈密顿路 邮递员在送信时，为了节省路途，自己规定：每次总是从n个村子中选择其中一个合适的村子出发，途经每个村子仅且经过一次，送完所有的信。已知各个村子的道路连通情况。请你帮邮递员选择一条合适的路线。输入：第一行：整数n(2=n=200)：村子的个数。接下来是一个n*n的0、1矩阵，表示n个村子的连同情况，如：ai,j=1，表示第i和第j个村子之间有路可走，如果ai,j=0，表示他们之间无路可走。输出：一条可行的路线输入：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第36页/共79页分析题目的限制条件：“途经每个村子仅且经过一次”，表明在深搜的过程中，Vi的邻接点中必须要有至少一个顶点是没有被访问过的。这样才能沿着该点继续DFS下去。如果恰能遍历全部结点，则找到一条路径，输出这条路径即可。怎样在DFS的过程中保存路径？如果在DFS的某一层出现了所有邻接点都被访问过了，则说明在上一层（以及更上层）的路由选择不正确，这时就要回溯到上层，换一个未被访问的结点,再次进行DFS，看能否走通。在换结点的时候，一定要清除前一个结点被访问过的标志信息，这就是所谓的“清理现场”的工作。如果不做这个操作，则求解几乎没有可能得到正确结果。第37页/共79页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.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)and(visitedj=0)then begin visitedj:=1;m:=m+1;bm:=j;dfs(j);visitedj:=0;m:=m-1;end;end;第38页/共79页 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.第39页/共79页算法二proceduredfs(i,k:integer);结点i是路上的第k个结点varj:integer;beginifk=nthenprint;forj:=1tondoif(aj,i=1)and(visitedj=0)thenbeginvisitedj:=1;bk+1:=j;dfs(j,k+1);visitedj:=0;end;end;Begininit;found:=0;fori:=1tondobeginfillchar(visited,sizeof(visited),0);m:=1;b1:=i;visitedi:=1;dfs(i,1);end;iffound=0thenwriteln(noroad);end.第40页/共79页3 3、安排座位、安排座位 n n个个客客人人围围着着一一个个桌桌子子吃吃饭饭，每每一一个个人人都都至至少少认认识识其其他他的的2 2个个客客人人。请请设设计计程程序序求求得得n n个个人人的的一一种种坐坐法法，使使得得每每个个人人都都认认识他左右的客人。识他左右的客人。输入输入:第一行第一行:n:n（吃饭人的个数）。（吃饭人的个数）。以下以下n n行：第行：第i i行的第一个数行的第一个数k k表示第表示第i i个人认识的人数，后面个人认识的人数，后面k k个数依次为个数依次为i i认识的人的编号。认识的人的编号。输出：所有座法，要求第一个人为输出：所有座法，要求第一个人为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第41页/共79页分析分析:如如果果A A认认识识B,BB,B又又认认识识C,C,则则B B认认识识他他左左右右的的两两个个人人.继继续续这这个个过过程程,如如果果C C又又认认识识D,D,则则C C认认识识他他左左右右的的两两个个人人;这这其其实实就就是一个是一个DFSDFS过程过程.如如果果最最后后一一个个人人能能认认识识第第一一个个人人,则则最最后后一一个个人人也也认认识识他他左左右右的两个人的两个人.这样就找到一组满足要求的解了这样就找到一组满足要求的解了.本题是求一个本题是求一个N N个顶点的简单回路问题个顶点的简单回路问题.第42页/共79页proceduredfs(i:integer);varj,k:integer;beginif(n=m)and(ab1,bm=1)thenprint;forj:=1tondoif(ai,j=1)and(visitedj=0)thenbeginvisitedj:=1;m:=m+1;bm:=j;dfs(j);visitedj:=0;m:=m-1;end;end;Begininit;fillchar(visited,sizeof(visited),0);found:=0;m:=1;b1:=1;visited1:=1;dfs(1);iffound=0thenwriteln(noroad);end.第43页/共79页4、素数链设计程序将1,2,20排成一排，使任意两个相邻的数的和为素数。第1个和最后一个的和也为素数.输出:120个数的排列方式.第44页/共79页const maxn=100;var visited:array1.maxnof 0.1;b:array1.maxn of 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;第45页/共79页 procedure dfs(i:integer);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);end.第46页/共79页2 2、广度（宽度）优先搜索、广度（宽度）优先搜索BFSBFS 广度优先搜索广度优先搜索按层次按层次遍历的过程，其搜索过程如下：遍历的过程，其搜索过程如下：方法：从图的某一顶点V1出发，访问此顶点后，依次访问V1的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V5 V6 V7 V8第47页/共79页V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8第48页/共79页V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V6 V7 V8 V5第49页/共79页在程序中实现BFS从图的某一顶点V1出发，访问此顶点后，依次访问V1的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；要解决的问题:怎样依次访问Vi的邻接点?怎样依次从它的邻接点出发,广度优选遍历图?我们用到的主要的数据结构就是队列.第50页/共79页例142350 1 2 3 4 51fr遍历序列：10 1 2 3 4 54fr遍历序列：1 40 1 2 3 4 54 3fr遍历序列：1 4 30 1 2 3 4 5fr队列空结点在入队时进行访问，f指针指向当前扩展结点11第51页/共79页0 1 2 3 4 54 3 2fr遍历序列：1 4 3 20 1 2 3 4 5 3 2fr遍历序列：1 4 3 20 1 2 3 4 5 3 2 5fr遍历序列：1 4 3 2 511 41 40 1 2 3 4 5 2 5fr遍历序列：1 4 3 2 50 1 2 3 4 5 5fr遍历序列：1 4 3 2 50 1 2 3 4 5 fr遍历序列：1 4 3 2 51 4 31 4 3 21 4 3 2 5第52页/共79页14356782输入：81014151626273534375758编程实现：输入下图，按深度优先遍历和广度优先遍历输编程实现：输入下图，按深度优先遍历和广度优先遍历输出图的结点。出图的结点。第53页/共79页图的dfsconstmax=100;vara:array1.max,1.maxofinteger;f:array1.maxof0.1;/标志数组n,m,i:integer;procedureinit;vari,j,x,y:integer;beginreadln(n,m);fillchar(f,sizeof(f),0);fori:=1tomdobeginreadln(x,y);ax,y:=1;ay,x:=1;end;end;proceduredfs(i:integer);深搜varj:integer;beginwrite(i,);fi:=1;forj:=1tondoif(fj=0)and(ai,j=1)thendfs(j);end;第54页/共79页procedurebfs(i:integer);广搜varj,k:integer;beginfillchar(q,sizeof(q),0);f:=0;队首r:=1;尾q1:=i;i进队列write(i,);fi:=1;标志whilefrdo队列不空begininc(f);k:=qf;出队forj:=1tondoif(ak,j=1)and(fj=0)thenbeginwrite(j,);fj:=1;inc(r);进队qr:=j;end;end;end;BEGINInit;/读入图数据,初始化标志数组For i:=1 to n do if fi=0 then dfs(i);Writeln;fillchar(f,sizeof(f),0);for i:=1 to n do if fi=0 then bfs(i);END.第55页/共79页 问题描述问题描述 学校放暑假时，信息学辅导教师有学校放暑假时，信息学辅导教师有n n本书要分给参加培训的本书要分给参加培训的n n个学生。个学生。如：如：A A，B B，C C，D D，E E共共5 5本书要分给参加培训的张、刘、王、李、孙本书要分给参加培训的张、刘、王、李、孙5 5位学生，位学生，每人只能选每人只能选1 1本。教师事先让每个人将自己喜爱的书填写在如下的表中，然本。教师事先让每个人将自己喜爱的书填写在如下的表中，然后根据他们填写的表来分配书本，希望设计一个程序帮助教师求出可能的后根据他们填写的表来分配书本，希望设计一个程序帮助教师求出可能的分配方案，使每个学生都满意。分配方案，使每个学生都满意。A AB BC CD DE E张张Y YY Y王王Y YY Y刘刘Y YY Y孙孙Y Y李李Y YY Y5 5、借书问题、借书问题第56页/共79页输入格式：第一行一个数n（学生的个数，书的数量）以下共n行，每行n个0或1（由空格隔开），第I行数据表示第i个同学对所有书的喜爱情况。0表示不喜欢该书，1表示喜欢该书。输出格式：依次输出每个学生分到的书号。样例：输入：book.in50 0 1 1 01 1 0 0 00 1 1 0 00 0 0 1 00 1 0 0 1输出：book.out3 1 2 4 5第57页/共79页分析:a:array1.maxn,1.maxnof 0.1;b:array1.maxnof integer;方案:bi是第i个人借第bi本书 book:array1.maxnof boolean;booki:能否可以借第i本书,初始:true,一旦有人借了:就改为:false第58页/共79页算法设计:procedure try(i:integer);搜索第i个人可以借的书bi var j:integer;begin if i=n+1 then 输出结果 else for j:=1 to n do if 第i个人可以借第j 本书 then begin 记录下bi;标记第j本数已被借;try(i+1);删除书的被借标志;end;end;第59页/共79页constmaxn=10;vara:array1.maxn,1.maxnof0.1;b:array1.maxnofinteger;book:array1.maxnofboolean;n:integer;procedureinit;vari,j:integer;beginassign(input,book.in);reset(input);fillchar(b,sizeof(b),0);fillchar(book,sizeof(book),true);readln(n);fori:=1tondoforj:=1tondoread(ai,j);close(input);end;procedureprint;vari:integer;beginfori:=1ton-1dowrite(bi,);writeln(BN);end;proceduretry(i:integer);varj:integer;beginifi=n+1thenprint;forj:=1tondoifbookjand(ai,j=1)thenbeginbi:=j;bookj:=false;try(i+1);bookj:=true;end;end;Begininit;try(1);end.第60页/共79页火力中心布局火力中心布局(自习自习)现有一张由n个堡垒组成的交通图，任意两个堡垒之间只有一条通行路线。为了确保路线畅通，必须在某些堡垒上建立火力中心，每个火力中心都能够对其相连的所有交通线进行全天候的监控，防止敌人侵略。现在的问题是如何设置火力中心的布局，才能用最少的火力中心控制所有交通路线。输入：堡垒数n(1n10000)；以下每行为i，j，表示堡垒i与堡垒j连接。以0 0标志结束；输出：w行，每行为火力中心所在的堡垒号。火力中心数w第61页/共79页数学模型和解题的基本思路数学模型和解题的基本思路 如果将堡垒设为顶点、堡垒间的交通线设为边的话，则交通图为一张无向图。由于任意两个堡垒之间只有一条通行路线，且没有明确出发点，因此这张无向图构成了一棵无根树。所谓支配集是图的一个满足下述条件的顶点子集：即图的任意顶点或属于该集合，或至少与该集合的一个顶点相邻。显然，火力点就是支配集中的顶点。本题的数学模型就是在交通图对应的无根树中，计算含顶点数最少的最小支配集。如果是一棵明确了顶点间父子关系的有根树的话，我们很容易找到计算最小支配集的方法：按照自底而上、由右而左的顺序搜索每一条边。如果一条边的两个端点为访问，则父顶点进入支配集，由其支配祖父顶点和所有儿子。依次类推，直至根被访问为止。第62页/共79页第一步：建立边表。第一步：建立边表。由于交通图为一张无向图，因此我们将每条边拆分成方向互为相反的两条边，即(xi，yi)作为第i条边存储，(yi，xi)作为第n+i条边存储:for i1 to n-1 do建立边表。由于是无向图，因此将第i条边（k,j）分别存储于（xi,yi）和（xn+i-1,yn+i-1）begin readln(f,xi,yi);读第i条边的两个端点 xi+n-1yi;yi+n-1xi反向存储第i条边的两个端点 end;for第63页/共79页第二步：通过深度优先搜索将无根树转化为明确顶点间父子关系的有第二步：通过深度优先搜索将无根树转化为明确顶点间父子关系的有根树。根树。首先从顶点1出发，按照纵深搜索的策略构造一棵深度优先搜索树，并记下每个顶点的父顶点。由于树边的父子关系未明确,因此逐边搜索。方向是由左而右、由上而下，对于第i个被访问的顶点来说，所有访问顺序比i大的顶点，不是该顶点的后辈顶点就是位于该顶点的右方树枝上。例如第64页/共79页设cd表为按照深度优先搜索顺序存储的被访问顶点，即第i个被访问的顶点为cdi。在深度优先搜索树中，其父亲为ptcdi。我们通过递归过程encode计算深度优先搜索的访问顺序表cd和父指针表pt：procedure encode(nw,last:integer);输入当前顶点nw和父顶点last，递归计算cd和pt表var i:integer;begin inc(nm);cdnmnw;nw进入深度优先搜索的访问顺序表 cvnwtrue