《图及其应用》课件.ppt

1、第15讲: 数据结构之 图,一、 图的基本概念,二、图的存储结构,三、图的遍历,四、无向图的传递闭包,五、最短 路径,六、最小生成树,七、拓扑排序,1、图的的定义 图是由顶点V的集合和边E的集合组成的二元组： 记G=（V，E） 存在一个结点v，可能含有多个前驱结点和后继结点。,一、 图的基本概念,无向图： 在图G=（V，E）中，如果对于任意的顶点a，bV， 当(a，b)E时，必有（b，a）E（即关系R对称），此图称为无向图。 无向图中用不带箭头的边表示顶点的关系 V=1, 2, 3, 4, 5 E=(1, 2),(1, 3),(1, 4),(2,3),(2,5),(3, 5),(4,5),2、

2、无向图和有向图,有向图： 如果对于任意的顶点a，bV，当(a，b)E时 ，(b，a)E未必成立，则称此图为有向图。 在有向图中，通常用带箭头的边连接两个有关联的结点。 V=1, 2, 3, 4,5 E= , , , , , ,在无向图中：顶点v的度是指与顶点v相连的边的数目。D( 2 )=3,3、顶点的度、入度和出度,在有向图中：入度以该顶点为终点的边的数目和 . ID(3)=2 出度以该顶点为起点的边的数目和 . OD(3)=1 度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。 度：等于该顶点的入度与出度之和。 D(5)=ID(5)+OD(5)=1+2=3,图中所有顶点的度=边的两倍,图1

3、,图2,完全图,4、 路径、简单路径、回路 在图G=（V，E）中，如果对于结点a，b，存在满足下述条件的结点序列x1xk(k1) x1=a，xk=b (xi，xi+1)E i=1k-1 则称结点序列x1=a，x2，xk=b为结点a到结点b的一条路径，而路径上边的数目（k-1）称为该路径的长度。,图1,图2,图1: 1、(1,2,3,5) 长度=3 2、(1,2,3,5,2) 长度=4 3、(1,2,5,4,1) 长度=4,图2: (1,2,5,4) 长度=3,（1）、如果一条路径上的结点除起点x1和终点xk可以相同外，其它结点均不相同，则称此路径为一条简单路径。 （2）、x1=xk的简单路径称

4、为回路（也称为环）,5、连通、连通图、连通分量 (无向图),直观理解： 连通：“连成一片”。 连通图：“能连成一片的图”。,图一,图二,确切定义： 连通：如果从顶点u到v有路径，则称u和v是连通的。 连通图：图中任意的两个顶点u和v都是连通的。,图一是连通图，图二是非连通图,连通分量：无向图中的极大连通子图。,图二中有3个连通分量： 1 2 4 5 3 6 7 8,求连通分量数，最大连通分量等。,有向图：强连通、强连通图、强连通分量,6、带权图,图中的边可以加上表示某种含义的数值，数值称为边的权，此图称为带权图。也称为网。,一般的图边上没有数字，边仅表示两个顶点的相连接关系。,二、图的存储结构

5、,1、邻接矩阵（静态数组） 2、邻接表（指针数组） 3、边集数组 4、十字链表 5、邻接多重表,图的邻接矩阵表示法 邻接矩阵是表示结点间相邻关系的矩阵。若G=（V，E）是一个具有n个结点的图，则G的邻接矩阵是如下定义的二维数组a。,1、邻接矩阵,ai,j=,1(或权值)：无向图：有边( i , j )和边( j , i ) 有向图：有边,0: i 到 j 无边,对角线为0：自身不相连。 无向图：是对称矩阵。有向图一般不是。 第i行非0 的个数是结点i的度,具体到题目时，数据的给出格式多种多样： 1）、直接给出邻接矩阵，直接读即可。 如： 输入文件内容： 50 2 2 3 02 0 1 0 32

6、 1 0 0 23 0 0 0 40 3 2 4 0,Maxn=100 A:array1.maxn,1.maxn of integer Fillchar(a,sizeof(a),0); Readln(n); For i:=1 to n do for j:=1 to n do read(aI,j);,2）、给出边的顶点。 如输入文件：两个顶点及权值 571 2 21 3 21 4 32 3 12 5 33 5 24 5 4,Readln(n); readln(m); For k:=1 to m do begin readln(I,j,x); aI,j:=x; aj,i:=x; end,2、邻接表

7、 :方法1,头指针,邻接点指针,type edge = node; node = record data : integer; weight : integer; next : edge; end; vpoint = record data : integer; link : edge; end; var a : array1.maxn of vpoint; / 具体操作：dfs2.pas,邻接表方法2：,权值单独用另外的数组W 设置结点指针,type point=node; node=record data:integer; next:point; end; var a:array1.max

8、vof point; /具体操作：dfs3.pas,三、图的遍历 给出一个图G，从某一个初始点出发，按照一定的搜索方法对图中的每一个结点访问仅且访问一次的过程。 访问结点：处理结点的过程。如输出结点的信息、求和等，根据题目要求。 按照搜索方案的不同，通常有两种遍历方法： 深度优先搜索dfs 广度优先搜索bfs,1、深度优先搜索DFS 遍历算法（递归过程）： 1)从某一初始出发点i开始访问： 输出该点编号；并对该点作被访问标志（以免被重复访问）。 2)再从i的其中一个未被访问的邻接点j作为初始点出发继续深搜。 当i的所有邻接点都被访问完，则退回到i的父结点的另一个邻接点k再继续深搜。 直到全部接

9、点访问完毕,procedure dfs(k:integer);/从k点出发遍历 var j:integer; /局部变量？ begin write(k, ); fk:=true; for j:=1 to n do if (fj=false)and(ak,j=1) then dfs(j); end;,/读入边的关系 readln(n); readln(m); for i:=1 to m do begin readln(x,y); ax,y:=1; ay,x:=1; end;,上图的遍历结果：,Dfs(1)?,procedure main; var i:integer; begin fillcha

10、r(f,sizeof(f),false); for i:=1 to n do if not fi then dfs(i); end;,2、广度优先搜索(宽度优先搜索）BFS 广度优先搜索按层次遍历的过程，其搜索过程如下： 假设从图中某结点i出发，在访问了i之后依次访问i的各个未曾访问的邻接点，然后分别从这些邻接点出发按广度优先搜索的顺序遍历图，直至图中所有可被访问的结点都被访问到。,procedure bfs(i:integer);/ bfs.pas var j,k:integer; begin fillchar(q,sizeof(q),0); open:=0; closed:=1; q1:=

11、i; write(i, ); fi:=true; while openclosed do begin inc(open); k:=qopen; for j:=1 to n do if (ak,j=1)and(fj=false) then begin write(j, ); fj:=true; inc(closed); qclosed:=j; end; end; end;,3、图的遍历的简单应用,1、犯罪团伙 警察抓到了n个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知道其中的一些罪犯之间相互认识，已知同一犯罪团伙的成员之间直接或间接认识。有可能一个犯

12、罪团伙只有一个人。请你根据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编号从1至n。 输入： 第一行：n（=1000,罪犯数量）， 第二行：m（5000，关系数量） 以下若干行：每行两个数：I 和j，中间一个空格隔开，表示罪犯i和罪犯j相互认识。 输出： 一个整数，犯罪团伙的数量。,样例输入： 11 8 1 2 4 3 5 4 1 3 5 6 7 10 5 10 8 9,输出： 3 说明：共三个犯罪团伙。,把n个人看成图的n个顶点；相互认识的连一条边。相互认识的所有人构成一个极大连通子图。 问题转化为：求无向图的连通分量 （有多少个极大连通子图）,procedure main; var

13、i:integer; begin sum:=0; fillchar(f,sizeof(f),false); for i:=1 to n do if not fi then begin inc(sum); dfs(i); end; writeln(sum); end;,2、邮递员,邮递员在送信时，为了节省路途，自己规定：每次总是从n个村子中选择其中一个合适的村子出发，途中每个村子仅且经过一次，送完所有的信。已知各个村子的道路连通情况。请你帮邮递员选择一条合适的路线。,输入： 第一行：整数n：村子的个数。 接下来是一个n*n的0、1矩阵，表示n个村子的连同情况，如：aI,j=1 ，表示第i和第j个

14、村子之间有路可走，如果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 4,分析： 邮递员从某一个村子A出发；每个村子访问仅且访问一次，最后到达村子B结束，从A到B的路线成为哈密顿路。 如果A和B重合，即回到出发点，称为哈密顿回路。,b:array1.maxn of integer; /记录哈密顿路,procedure main; var i:integer;

15、begin for i:= 1 to n do begin fillchar(visited,sizeof(visited),false); b1:=i; visitedi:=true; dfs(i,1); end; print(0); end;,procedure dfs(i,k:integer); /当前已找到有k个点，要搜第k+1个点 var j:integer; begin if k=n then print(1); for j:=1 to n do if (aj,i=1) and (visitedj=false) then begin visitedj:=true; bk+1:=j;

16、/找到第k+1个点并记下 dfs(j,k+1); visitedj:=false; /回溯 end; end;,怎样求哈密顿回路？,3 、安排座位 n个客人围着一个桌子吃饭，每一个人都至少认识其他的2个客人。请设计程序求得n个人的一种坐法，使得每个人都认识他左右的客人。,输入: 第一行:n（吃饭人的个数）。 以下n行：第i行的第一个数k表示第i个人认识的人数，后面k个数依次为i认识的人的编号。 输出：所有座法，要求第一个人为1号作为起点，按顺时针输出其它人的编号。,样例输入： 6 2 3 6 3 4 5 6 3 1 4 6 3 2 3 5 3 2 4 6 4 1 2 3 5,样例输出： 1 3

17、 4 2 5 6 1 3 4 5 2 6 1 6 2 5 4 3 1 6 5 2 4 3,4、素数链 设计程序将1。n（20）排成一排，使任意两个相邻的数的和为素数。第1个和最后一个的和也为素数. 输出:第一个数为1.,四、无向图的传递闭包,判断无向图的连通性,1,2,3,4,6,5,7,输入图的边的信息，输出各点的连通行。,输入： 7 1 2 2 3 1 3 3 4 5 6 6 7,输出： 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1,0 1

18、1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0,邻接矩阵,判断结点 i 和 j的连通性：,1、结点i和j如果原来有边则连通。 2、如果i和j之间没有边： 如果存在另外的一个结点k，满足：i与k连通，k与j连通，则i与j连通。 否则i和j不连通。,Can i , j : true ，i与j之间有边；false：无边。 则：Can i , j =can i , j or ( can i , k and can k , j ),for k:=1 to n do

19、for i:=1 to n do for j:=1 to n do cani,j:=cani,j or (cani,k and cank,j);,过程：,产生数 【问题描述:】 给出一个正整数 n（n 5 3 6 上面的整数 234 经过变换后可能产生出的整数为（包括原数）: 234 534 264 564 共 4 种不同的产生数。 【任务：】 给出一个整数 n 和 k 个变换规则。 求经过任意次的变换（0次或多次），能产生出多少个不同整数。仅要求输出个数。 【输入：】 第一行：n。第二行：k。以下k行：每行两个一位数：x y，中间一个空格，表示一个变换规则：x可以变为y。 【输出：】 一个整

20、数（满足条件的个数）： 【输入样例：】 234 2 2 5 3 6 【样例输出：】 4,应用举例,本题搜索显然是不行的。 对于只需计数而不需求具体方案的题目，一般都不会用搜索解决。,分析：,乘法原理直接进行计数。 用Fi表示数字i包括本身可以变成的数字总个数 这里的变成可以是直接变成也可以是间接变成： 比如 3-5, 5-7,那么 3-7 那么对于一个数a（用数组存,长度为n），根据乘法原理它能产生出不同整数数量： Fa1*Fa2*Fa3*Fan,引例：,现在，我们想从城市A到达城市E。怎样走才能使得路径最短，最短路径的长度是多少？,五、图的最短路径,已知各个城市之间的道路情况如下：,图中两点

21、间的最短距离。 两类问题： 1、图中每对顶点（任意两点）之间的最短路径 （弗洛伊德算法：floyed）。 2、图中一个顶点到其他顶点的最短路径 （迪杰斯特拉算法：dijkstra）。,一）、计算每一对顶点间的最短路径（floyd算法）,目标：把图中任意两点i与j之间的最短距离都求出来 dI,j。 原理：根据图的传递闭包思想：,if dI,k+dk,jdI,j then dI,j=dI,k+dk,j,for k:=1 to n do for i:=1 to n do for j:=1 to n do if di,k+dk,jdi,j then di,j:=di,k+dk,j;,算法写法1：flo

22、yed2.pas,初始化条件： D i, i =0 /自己到自己为0；对角线为0； DI,j=边权，i与j有直接相连的边 DI,j= + ，i与j无直接相连的边。 / 一般设为： maxint or maxlongint;,举例： 已知下图中给定的关系，求出图中任意给定两点之间的最短距离,输入： 5 1 5 1 2 23 1 3 17 1 5 49 2 3 5 2 4 13 4 5 7,要求：输出最短距离d1,5。 / floyed2.pas,分析：,DI,j:表示顶点i到顶点j之间的最短距离。 初始化如下：,0 23 17 23 0 5 15 17 5 0 13 0 749 7 0,proc

23、edure init; readln(n); readln(p,q); for i:=1 to n do for j:=1 to n do if i=j then di,j:=0 else di,j:=maxint; while not seekeof do begin readln(i,j,w); di,j:=w; dj,i:=w; end;,procedure floyed; begin for k:=1 to n do for i:=1 to n do for j:=1 to n do if di,k+dk,jdi,j then di,j:=di,k+dk,j; end;,procedu

24、re print; begin writeln(dp,q); end;,算法写法2：floyed1.pas,0 23 17 0 023 0 5 15 017 5 0 0 00 13 0 0 749 0 0 7 0,初始化：无边的全都为0,procedure init; fillchar(d,sizeof(d),0); readln(n); readln(p,q); while not seekeof do begin readln(i,j,w); di,j:=w; dj,i:=w; end;,/ floyed for k:=1 to n do for i:=1 to n do if (ki)a

25、nd(di,k0) then for j:=1 to n do if (kj)and(ij)and(dk,j0) then if (di,j=0)or(di,k+dk,jdi,j) then di,j:=di,k+dk,j; / i与j无边时di，j=0,floyed输出最短路径路线,1-2: 22: 1 3 2 1-3: 17: 1 3 1-4: 35: 1 3 2 4 1-5: 42: 1 3 2 4 5 2-3: 5: 2 3 2-4: 13: 2 4 2-5: 20: 2 4 5 3-4: 18: 3 2 4 3-5: 25: 3 2 4 5 4-5: 7: 4 5,方法一：floye

26、d3.pas,设 pathI,j 记录i到j的最短路径中j的前驱顶点。 如样例： 1-4: 35: 1 3 2 4 path1,4=2path1,2=3path1,3=1,初始化： i到j有边，则 pathI,j:=I; pathj,i :=j,for k:=1 to n do for i:=1 to n do for j:=1 to n do if di,k+dk,jdi,j then begin di,j:=di,k+dk,j; pathi,j:=pathk,j; end;,/输出i到j的路线 procedure dfs(i,j:integer); begin if i=j then wr

27、ite(i, ) else if pathi,j0 then begin dfs(i,pathi,j); write(j, ); end; end;,方法二：floyed4.pas,设 pathI,j 记录能使i到j的距离变短的结点。,初始化： pathI,j= -1: i与j不通的 pathI,j:=0; 从i到j的最短路径是直接到达的。开始有边的都直接到达。 PathI,j0;从i到j的最短路径要经过点pathI,j.,for k:=1 to n do for i:=1 to n do for j:=1 to n do if di,k+dk,jdi,j then begin di,j:=d

28、i,k+dk,j; pathi,j:=k; end;,procedure dfs(i,j:integer);/ 输出i到j之间的点，不包含i和j结点； begin if pathi,j0 then begin dfs(i,pathi,j); write(pathi,j, ); dfs(pathi,j,j); end; end;,输出i到j的最短路径： Write(i); dfs(I,j); write(j);,总结： Floyed算法： 要求某两点之间 u 到 v 的最短距离，先求出任意两点之间的距离， 然后writeln(du,v),时间复杂度：O（n3）,二）、计算某一顶点到其它所有顶点的

29、最短路径 （单源最短路径问题：dijkstra 算法）,开始点（源点）：start Di:顶点到st的最短距离。 初始： Dstart=0； Di=ast,i,start,其它n-1个点,集合1：已求点,集合2：未求点,1、在集合2中找一个到start距离最近的顶点k ，距离=dk,2、把顶点k加到集合1中，同时修改集合2 中的剩余顶点j的dj是否经过k后变短。如果变短修改dj If dk+ak,jdj then dj=dk+ak,j,3、重复1，直至集合2空为止。,for i:=1 to n do begin di:=astart,i; fi:=false; end; fstart:=tru

30、e; / 加入集合1 for i:=2 to n do begin min:=maxint; for j:=1 to n do if (not fj) and (djmin) then begin min:=dj; k:=j; end; fk:=true; / 加入集合1 for j:=1 to n do /修改集合2中的dj if (not fj) and (dk+ak,jdj) then dj:=dk+ak,j; end;,dijkstra 算法,Writeln(dstrat,mb),输入： 5 1 1 2 23 1 3 17 1 5 49 2 3 5 2 4 13 4 5 7,1-2:

31、22: 1 3 2 1-3: 17: 1 3 1-4: 35: 1 3 2 4 1-5: 42: 1 3 2 4 5,怎样输出路径？,六、图的最小生成树,普里姆算法（prim） 克鲁斯卡尔（kruskal）,网络建设 Net.pas/net.in/net.out 【问题描述：】 OI国由n个城市组成，所有城市位于一平面坐标系中，每个城市的坐标是已知的，且坐标都是整数。现在，OI国的CHEN主席想加快网络信息传递，决定选若干对城市，每对城市之间用一条高速网线相连，并且使所有的城市都可以直接或间接相连。已知两城市之间的距离为它们的直线距离，求所需网线的最小长度。 【输入：】 n n行，每行有两个整

32、数x , y 表示第i个城市的坐标为 (x , y ) 【输出：】 最短的网线的长度。 结果保留3为小数。,【输入样例：】 6 2 1 4 1 5 4 3 5 3 3 2 3,【输出样例：】 9.236 数据规模 n=500 1= x, y =1000,0 1 2 3 4 5 6,2 1,3,4,5,6,1,2,4,3,5,17,30,10,24,7,23,5,最小生成树： 含有n个结点的图，从中选n-1条边，保持n个点中任意两点是连通的，并且n-1条边的和最小。这n个点和这n-1条边就成为原图的最小生成树。,任意结点开始（不妨设为v1）构造最小生成树： 首先把这个结点包括进生成树里，然后在那

33、些其一个端点已在生成树里、另一端点还未在生成树里的所有边中找出权最小的一条边，并把这条边、包括不在生成树的另一端点包括进生成树，。依次类推，直至将所有结点都包括进生成树为止。,普里姆算法（prim）,1,2,4,3,5,17,30,10,24,7,23,5,1,2,3,4,5,for i:=1 to n do begin di:=a1,i; fi:=false; end; f1:=true; /放在生成树中 ans:=0; for i:=2 to n do begin min:=maxint; for j:=1 to n do if (not fj) and (djmin) then begi

34、n min:=dj; k:=j; end; inc(ans,dk); fk:=true; for j:=1 to n do if (not fj) and(ak,jdj) then dj:=ak,j; end;,Prim算法描述：,/ai，j：i到j的边长。 /Di：结点i到生成树中结点的最短距离 /fi:true:在生成树种，false：不在生成树中。,输入： 5 1 2 23 1 3 17 1 5 49 2 3 5 2 4 13 4 5 7,输出最小生成树的边：,pre:array1.maxn of integer; prei:点i的前驱点 tree:array1.maxn-1,1.2 o

35、f integer; 记录边,for i:=1 to n do begin di:=a1,i; prei:=1; fi:=false; end; f1:=true; ans:=0; for i:=1 to n-1 do begin min:=maxint; for j:=1 to n do if (not fj) and (djmin) then begin min:=dj; k:=j; end; treei,1:=k; treei,2:=prek; inc(ans,dk); fk:=true; for j:=1 to n do if (not fj) and(ak,jdj) then beg

36、in dj:=ak,j; prej:=k; end; end;,克鲁斯卡尔（kruskal）,算法步骤： 1、把图中的边按权值从小到大排序。 2、按从小到大的顺序依次向树中加边。 在添加每一条边（u，v）时，如果u和V两个点都已在树中，一旦添加，就回构成回路，所以放弃该边，在向后找下一条边。 3、直到添加n-1条边。,关键：加边时不能构成回路：边的两个顶点是否已在树种。,1,2,4,3,5,17,30,10,24,7,23,5,1,2,3,4,5,type node=record data:integer; u,v:integer; end; var e:array1.maxn*(maxn-1) div 2 of node; /边 f:array1.maxn of integer; /父亲接点 n,m:integer; ans:integer;,readln(n); m:=0; while not seekeof do begin readln(i,j,k); inc(m); em.data:=k; em.u:=i; em.v:=j; end;,procedure kruskal; var i:integer; begin sort; for i:=1 to n do fi:=0; /初始化根为0 ans:=0; for i:=1 to m