图及其应用(2009烟台夏令营赵宗昌)

1、数据结构之数据结构之 图图山东师大附中山东师大附中 赵宗昌赵宗昌 2009/07/202009/07/20一、图的基本概念一、图的基本概念二、图的存储结构二、图的存储结构三、图的遍历三、图的遍历四、无向图的传递闭包四、无向图的传递闭包五、最短路径五、最短路径六、最小生成树六、最小生成树七、拓扑排序七、拓扑排序内容：内容： 图是由一个顶点的集合图是由一个顶点的集合V V和一个顶点间关系的集合和一个顶点间关系的集合E E组成：组成： 记记 G=G=（V V，E E） V V：顶点的有限：顶点的有限非非空集合。空集合。 E E：顶点间关系的有限集合（边集）。：顶点间关系的有限集合（边集）。 存在一个

2、结点存在一个结点v v，可能含有多个前驱结点和后继结点。，可能含有多个前驱结点和后继结点。一、一、 图的基本概念图的基本概念125341253412534图图2图图3图图1 1 1、图的的定义、图的的定义无向图：无向图： 在图在图G=G=（V V，E E）中，如果对于任意的顶点）中，如果对于任意的顶点a a，bVbV，当当(a(a，b)Eb)E时，必有（时，必有（b b，a a）EE（即关系（即关系R R对称），此图称为对称），此图称为无向图。无向图。无向图中用不带箭头的边表示顶点的关系无向图中用不带箭头的边表示顶点的关系 V=1, 2, 3, 4, 5 E=(1, 2),(1, 3),(1,

3、 4),(2,3),(2,5),(3, 5),(4,5) 125342、无向图和有向图、无向图和有向图有向图：有向图： 如果对于任意的顶点如果对于任意的顶点a a，bVbV，当，当(a (a，b)Eb)E时时 ，(b(b，a)Ea)E未未必成立，则称此图为有向图。必成立，则称此图为有向图。在有向图中，通常用带箭头的边连接两个有关联的结点。在有向图中，通常用带箭头的边连接两个有关联的结点。V=1, 2, 3, 4,5 V=1, 2, 3, 4,5 E= , , , , , E= , , , , , 12534在无向图中：顶点在无向图中：顶点v v的度是指与顶点的度是指与顶点v v相连的边的数目相

4、连的边的数目D(vD(v) )。D(2)=3D(2)=33 3、顶点的度、入度和出度、顶点的度、入度和出度在有向图中在有向图中：入度入度以该顶点为终点的边的数目和以该顶点为终点的边的数目和 . ID(3)=2 . ID(3)=2 出度出度以该顶点为起点的边的数目和以该顶点为起点的边的数目和 . OD(3)=1. OD(3)=1度数为奇数的顶点叫做度数为奇数的顶点叫做奇点奇点，度数为偶数的点叫做，度数为偶数的点叫做偶点偶点。度度：等于该顶点的入度与出度之和。：等于该顶点的入度与出度之和。 D(5)=ID(5)+OD(5)=1+2=3D(5)=ID(5)+OD(5)=1+2=3 125341253

5、4结论：图中所有顶点的度结论：图中所有顶点的度=边边数的两倍数的两倍1( )2*niiD ve图图1:无向图无向图图图2：有向图：有向图*(1)2nne无向完全图无向完全图 在图在图G=G=（V V，E E）中，如果对于结点）中，如果对于结点a a，b b，存在满足下述条件的结点序列，存在满足下述条件的结点序列x x1 1xxk k(k (k1)1) x x1 1=a=a，x xk k=b =b (x (xi i，x xi+1i+1)E i=1)E i=1k-1k-1则称结点序列则称结点序列x x1 1=a=a，x x2 2，x xk k=b=b为结点为结点a a到结点到结点b b的一条路径，

6、而路径上边的一条路径，而路径上边的数目（的数目（k-1k-1）称为该路径的长度。）称为该路径的长度。1253412534图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 4、路径、简单路径、

7、回路、路径、简单路径、回路5、连通、连通图、连通分量、连通、连通图、连通分量 (无向图无向图)连通：连通：“连成一片连成一片”。连通图：连通图：“能连成一片的图能连成一片的图”。1253412534678图一：连通图图一：连通图图二：非连通图图二：非连通图定义：定义：连通连通：如果存在一条从顶点：如果存在一条从顶点u u到到v v有路径，则称有路径，则称u u和和v v是连通的。是连通的。连通图连通图：图中任意的两个顶点：图中任意的两个顶点u u和和v v都是连通的，称为连通图。都是连通的，称为连通图。 否则称为非连通图。否则称为非连通图。连通分量连通分量：无向图中的：无向图中的极大连通子图极

8、大连通子图。图二中有图二中有3 3个连通分量：个连通分量：1 2 4 5 3 6 7 81 2 4 5 3 6 7 8求连通分量数，最大连通分量等。求连通分量数，最大连通分量等。有向图：强连通、强连通图、强连通分量有向图：强连通、强连通图、强连通分量 6、带权图、带权图 图中的边可以加上表示某种含图中的边可以加上表示某种含义的数值，数值称为边的权，此图义的数值，数值称为边的权，此图称为带权图。也称为网。称为带权图。也称为网。 一般的图边上没有数字，边仅表示一般的图边上没有数字，边仅表示两个顶点的相连接关系。两个顶点的相连接关系。12534234213212534二、图的存储结构二、图的存储结构

9、ABDCE12345顶点：数组或记录顶点：数组或记录边：边：邻接矩阵邻接矩阵/邻接表邻接表 G=( V,E ) 邻接矩阵是表示结点间相邻关系的矩阵。若邻接矩阵是表示结点间相邻关系的矩阵。若G=G=（V V，E E）是一个具有是一个具有n n个结点的图，则个结点的图，则G G的邻接矩阵是如下定义的二维的邻接矩阵是如下定义的二维数组数组 a1.n,1.na1.n,1.n。ai,j=1 (或权值或权值)：无向图：有边：无向图：有边( i , j )和边和边( j , i ) 有向图：有边有向图：有边0: i 到到 j 无边无边1、图的邻接矩阵表示法、图的邻接矩阵表示法125340 1 1 1 01

10、0 1 0 11 1 0 0 11 0 0 0 10 1 1 1 01 2 3 4 51 23451253423421320 2 2 3 02 0 1 0 32 1 0 0 23 0 0 0 40 3 2 4 01 2 3 4 51 2345125340 1 0 1 00 0 1 0 11 0 0 0 00 0 0 0 00 0 1 1 01 2 3 4 51 2345对角线为对角线为0：自身不相连。：自身不相连。无向图：是对称矩阵。有向图一般不是。无向图：是对称矩阵。有向图一般不是。第第i行非行非0 的个数是结点的个数是结点i的度的度具体到题目时，数据的给出格式多种多样：具体到题目时，数据的

11、给出格式多种多样：1）、直接给出邻接矩阵，直接读即可。）、直接给出邻接矩阵，直接读即可。如：如：输入文件内容：输入文件内容：50 2 2 3 02 0 1 0 32 1 0 0 23 0 0 0 40 3 2 4 0maxn=100a:array1.maxn,1.maxn of integerfillchar(a,sizeof(a),0);readln(n);for i:=1 to n do for j:=1 to n do read(ai,j);1253423421322）、）、给出边的顶点。给出边的顶点。如输入文件：两个顶点及权值如输入文件：两个顶点及权值571 2 21 3 21 4 3

12、2 3 12 5 33 5 24 5 4125342342132readln(n); readln(m);for k:=1 to m do begin readln(i,j,x); ai,j:=x; aj,i:=x; end62 3 63 4 5 63 1 4 63 2 3 53 2 4 64 1 2 3 51235463)、给出每个顶点的邻接点、给出每个顶点的邻接点 readln(n); for i:=1 to n do begin read(k); for j:=1 to k do begin read(x); ai,x:=1;ax,i:=1; end; end;125344无权图无权图:

13、设置结点指针设置结点指针结点结点邻接点指针邻接点指针2、邻接表、邻接表 :1234523413512515234邻结点邻结点头结点头结点type point=node; node=record v:integer; next:point; end;var a:array1.maxvof point;vnext readln(n1,n2); new(p); p.v:=n2; p.next:=an1; an1:=p; new(p); p.v:=n1; p.next:=an2; an2:=p;125342342132123452232431231531221521354233244头指针头指针邻接点

14、指针邻接点指针结点结点邻接点指针邻接点指针邻接点邻接点边权值边权值下一个邻接点指针下一个邻接点指针有权图：有权图：type edge = node; node = record v: integer; weight : integer; next : edge; end; vpoint = record v: integer; link : edge; end;var a : array1.maxn of vpoint;vlinkvweightnext邻接矩阵和邻接表的优缺点：邻接矩阵和邻接表的优缺点：125340 1 1 1 01 0 1 0 11 1 0 0 11 0 0 0 10 1 1

15、 1 01 2 3 4 51 23451234523413512515234邻结点邻结点头结点头结点邻接表邻接表邻接矩阵邻接矩阵邻接矩阵：代码书写简单，找邻接点慢邻接矩阵：代码书写简单，找邻接点慢邻接表：代码书写较复杂，找邻接点快邻接表：代码书写较复杂，找邻接点快一般采用邻接矩阵一般采用邻接矩阵1763245980 1 0 0 0 0 0 0 01 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 10 0 0 0 0 0 1 0 00 0 0 0 0 1 0 0 00 0 0 0 0 0 0 0 00 0 0 0

16、 1 0 0 0 01234521679邻结点邻结点头结点头结点67895邻邻接接表表邻接矩阵邻接矩阵稀疏图：边表稀疏图：边表 type node=record w:integer; /边权边权 u,v:integer; /两个结点两个结点 end; var e: array1.maxn*(maxn-1) div 2 of node; /边边三、图的遍历三、图的遍历 给出一个图给出一个图G G，从某一个初始点出发，按照一定的搜索方法对，从某一个初始点出发，按照一定的搜索方法对图中的每一个结点访问图中的每一个结点访问仅且访问一次仅且访问一次的过程。的过程。 访问结点：处理结点的过程。如输出访问结

17、点：处理结点的过程。如输出、查找、查找结点的信息结点的信息。 按照搜索方按照搜索方法法的不同，通常有两种遍历方法：的不同，通常有两种遍历方法： 1 1、深度优先搜索深度优先搜索dfsdfs 2 2、广度优先搜索广度优先搜索bfsbfs 1 1、深度优先搜索、深度优先搜索DFSDFS遍历算法（递归过程）：遍历算法（递归过程）： 1) 1)从某一初始出发点从某一初始出发点i i开始访问：开始访问： 输出该点编号；并对该点输出该点编号；并对该点作被访问标志（以免被重复访问）。作被访问标志（以免被重复访问）。 2) 2)再从再从i i的其中一个未被访问的邻接点的其中一个未被访问的邻接点j j作为初始点

18、出发继续作为初始点出发继续深搜。深搜。 当当i i的所有邻接点都被访问完，则退回到的所有邻接点都被访问完，则退回到i i的父结点的另一个的父结点的另一个邻接点邻接点k k再继续深搜。再继续深搜。直到全部直到全部结结点访问完毕点访问完现实现:a1.maxn,1.maxn:边的邻接矩阵。边的邻接矩阵。1：有边；：有边；0：无边：无边f1.maxn:boolean 标记是否被访问过。标记是否被访问过。 True: 已访问；已访问；flase：没访问。初始值：没访问。初始值：false10121 41 51 64 8 5 34 35 76 27 102 93 77 2Proc

19、edure init; /初始化初始化 begin readln(n); readln(m); for i:=1 to m do begin readln(x,y); ax,y:=1; ay,x:=1; end; end;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;上图的遍历结果：上图的遍历结果：Dfs(1)?主程序主程序begin

20、fillchar(f,sizeof(f),false); for i:=1 to n do if not fi then dfs(i);end;求无向的连通分量求无向的连通分量 sum:=0; for i:=1 to n do if not fi then begin inc(sum); dfs(i); end; writeln(sum);125346782 2、广度优先搜索、广度优先搜索( (宽度优先搜索）宽度优先搜索）BFSBFS 按层次按层次遍历：遍历： 从图中某结点从图中某结点i i出发，在访问了出发，在访问了i i之后依次访问之后依次访问i i的各个未曾访问的各个未曾访问的邻接点，然

21、后分别从这些邻接点出发按广度优先搜索的顺序遍的邻接点，然后分别从这些邻接点出发按广度优先搜索的顺序遍历图，直至图中所有可被访问的结点都被访问到。历图，直至图中所有可被访问的结点都被访问到。1435678291014356782910实现：实现： 队列：队列：q1.maxn f1.n:boolean: 判重判重headtailprocedure bfs(i:integer);/ bfs.pas var j,k:integer; begin fillchar(q,sizeof(q),0); head:=0; tail:=1; q1:=i; fi:=true; while headtail do /

22、队列非空队列非空 begin inc(head); /出队出队 k:=qhead; write(k, ); for j:=1 to n do if (ak,j=1)and(fj=false) then begin inc(tail); /进队进队 qtail:=j; fj:=true; end; end; end;3、图的遍历的简单应用、图的遍历的简单应用1 1、犯罪团伙、犯罪团伙【问题描述【问题描述】 警察抓到了警察抓到了n个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知道其中的一些罪犯之间相不能判

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

24、犯和罪犯j相互认识。相互认识。【输出【输出】 一个整数，犯罪团伙的数量。一个整数，犯罪团伙的数量。【样例输入【样例输入】118 1 24 53 41 35 67 105 108 9【样例输出【样例输出】 3样例说明：共三个集团。样例说明：共三个集团。把把n个人看成图的个人看成图的n个顶点；相互认识的连一无向条边。个顶点；相互认识的连一无向条边。相互认识的所有人构成一个极大连通子图。相互认识的所有人构成一个极大连通子图。问题转化为：问题转化为：求无向图的连通分量求无向图的连通分量 （有多少个极大连通子图）（有多少个极大连通子图）1234106579811 建图建图 fillchar(f,size

25、of(f),false); /访问标志访问标志 sum:=0; for i:=1 to n do if not fi then begin inc(sum); dfs(i); end; writeln(sum); 算法：算法：12354672、邮递员邮递员 邮递员在送信时，为了节省路途，自己规定：每次总是从邮递员在送信时，为了节省路途，自己规定：每次总是从n个村子中选择个村子中选择其中一个合适的村子出发，途中每个村子其中一个合适的村子出发，途中每个村子仅且经过一次仅且经过一次，送完所有的信。已知，送完所有的信。已知各个村子的道路连通情况。请你帮邮递员选择一条合适的路线。各个村子的道路连通情况。

26、请你帮邮递员选择一条合适的路线。输入：输入：第一行：整数第一行：整数n：村子的个数。：村子的个数。接下来是一个接下来是一个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输出：输出：

27、2 3 7 6 5 1 4分析：分析： 邮递员从某一个村子邮递员从某一个村子A出发；每个村子访问仅且访问一次，最后到出发；每个村子访问仅且访问一次，最后到达村子达村子B结束，从结束，从A到到B的路线成为的路线成为哈密顿路哈密顿路。 如果如果A和和B重合，即回到出发点，称为重合，即回到出发点，称为哈密顿回路哈密顿回路。b:array1.maxn of integer; /记录哈密顿路记录哈密顿路 读入图：读入图：ai,j for i:= 1 to n do begin fillchar(visited,sizeof(visited),false); b1:=i; visitedi:=true;

28、dfs(i,1); end; print(0); procedure dfs( i, k: integer);/从结点从结点i开始找，已找到有开始找，已找到有k个点，要搜第个点，要搜第k+1个点个点 i是路上的第是路上的第k个点。个点。 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;/找到第找到第k+1个点并记下个点并记下 dfs(j,k+1); visitedj:

29、=false; /回溯回溯 end; end;怎样求哈密顿回路？怎样求哈密顿回路？procedure print(k:integer);/输出输出 var i:integer; begin if k=0 then writeln(no round) else begin for i:=1 to n-1 do write(bi, ); writeln(bn); end; halt; end; 3 3 、安排座位、安排座位 n n个客人围着一个桌子吃饭，每一个人都至少认识其他的个客人围着一个桌子吃饭，每一个人都至少认识其他的2 2个客人。请设计程序个客人。请设计程序求得求得n n个人的一种坐法，使

30、得每个人都认识他左右的客人。个人的一种坐法，使得每个人都认识他左右的客人。输入输入: :第一行第一行: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

31、3 4 2 5 61 3 4 5 2 61 6 2 5 4 31 6 5 2 4 3123546构造无向图，找一条哈密顿回路构造无向图，找一条哈密顿回路 readln(n); for i:=1 to n do begin read(k); for j:=1 to k do begin read(x); ai,x:=1;ax,i:=1; end; end;建图：建图： procedure dfs(i,k:integer);/从从i点开始找点，已有点开始找点，已有m个点个点 var j:integer; begin if (k=n)and(ab1,bk=1) then print(1); for

32、j:=1 to n do if (ai,j=1) and (visitedj=0) then begin visitedj:=1; bk+1:=j; dfs(j,k+1); visitedj:=0; end; end; procedure main; begin fillchar(visited,sizeof(visited),0); b1:=1; visited1:=1; dfs(1,1); print(0); end;4 4、素数链、素数链设计程序将设计程序将1 1。n n（2020）排成一排，使任意两个相邻的数的和为素数。）排成一排，使任意两个相邻的数的和为素数。第第1 1个和最后一个的

33、和也为素数个和最后一个的和也为素数. .输出输出: :第一个数为第一个数为1.1.如：如：样例输入：样例输入：6 6样例输出：样例输出：1 4 3 2 5 61 4 3 2 5 6主程序 fillchar(visited,sizeof(visited),0); b1:=1; visited1:=1; dfs(1,1);b1.maxn:记录结果序列。记录结果序列。Visited1.maxn: 标记是否已用过标记是否已用过搜索过程 procedure dfs(i,k:integer); /已找到第k个数是i，找第k+1个 var j:integer; begin if (n=k)and(check

34、(b1+bk) then print(1); for j:=1 to n do if (visitedj=0) and (check(i+j) then begin visitedj:=1; bk+1:=j; dfs(j,k+1); visitedj:=0; end; end;判读素数 function check(i:integer):boolean; var j:integer; begin for j:=2 to i-1 do if i mod j=0 then exit(false); exit(true); end;优化：建立素数表 maxn Prime3.2*maxn-1: boo

35、lean 素数：true；非素数：false 筛选法建立素数表筛选法求素数 for i:=1 to n do primei:=true; prime1:=false; for i:=2 to trunc(sqrt(n) do if primei then begin j:=2*i; while j=n do begin primej:=false; j:=j+i; end; end;四、图的传递闭包四、图的传递闭包G=( V, E )问题：顶点问题：顶点 i到到j是否存在一条从是否存在一条从i到到j的路径？的路径？G的传递闭包：的传递闭包： G*=（V，E*）E*=（i，j）：图）：图G中存在

36、一条中存在一条i到到j的路径的路径判断无向图的连通性判断无向图的连通性12346571 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 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 邻接矩阵邻接矩阵G*G传递闭包的算法：传递闭包的算法：ijk1、结点、结点 i 到到 j 有边则有路径。有边则有路径。2、

37、i 到到 j 之间没有边：之间没有边： 如果存在另外的一个结点如果存在另外的一个结点k，满足：，满足：i到到k有路径，有路径，k到到j有路径，则有路径，则i到到j有有路径。否则路径。否则i到到j没有路径。没有路径。can i , j =true:i到到j有边；有边； can i , j = false:无边。无边。则：则：can i , j =can i , j or ( can i , k and can k , j )判断结点判断结点 i 到到 j是否有路径是否有路径fillchar(f,sizeof(f),false);for i:=1 to n do fi,i:=true; for k

38、:=1 to n do for i:=1 to n do for j:=1 to n do cani,j:=cani,j or (cani,k and cank,j);过程：过程：产生数产生数(noip2001)【问题描述【问题描述:】给出一个正整数给出一个正整数 n（n1050) 和和 k 个变换规则（个变换规则（k 5 3 6上面的整数上面的整数 234 经过变换后可能产生出的整数为（包括原数）经过变换后可能产生出的整数为（包括原数）:234 534 264 564 共共 4 种不同的产生数。种不同的产生数。【任务：【任务：】给出一个整数给出一个整数 n 和和 k 个变换规则。个变换规则。

39、求经过任意次的变换（求经过任意次的变换（0次或多次），能产生出多少个不同整数。仅要求输出个数。次或多次），能产生出多少个不同整数。仅要求输出个数。 【输入：【输入：】第一行：第一行：n。第二行：。第二行：k。以下。以下k行：每行两个一位数：行：每行两个一位数：x y，中间一个空格，表示一个，中间一个空格，表示一个变换规则：变换规则：x可以变为可以变为y。【输出：【输出：】一个整数（满足条件的个数）：一个整数（满足条件的个数）： 【输入样例：【输入样例：】234 22 53 6【样例输出：【样例输出：】4应用举例应用举例分析：分析： 本题搜索本题搜索显然显然是不行的。是不行的。 对于只需计数而不

40、需求具体方案的题目，一般对于只需计数而不需求具体方案的题目，一般都不会用搜索解决。都不会用搜索解决。 234 72 52 85 75 17 93 64 32579184362: 63: 24: 36*2*3=36 乘法原理直接进行计数。乘法原理直接进行计数。 用用fi表示数字表示数字i包括本身可以变成的数字总个数包括本身可以变成的数字总个数 这里的变成可以是直接变成也可以是间接变成：这里的变成可以是直接变成也可以是间接变成： 比如比如 3-5, 5-7,那么那么 3-7那么对于一个数那么对于一个数a（用数组存（用数组存,长度为长度为n），根据乘法原理），根据乘法原理它能产生出不同整数数量：它能

41、产生出不同整数数量：fa1*fa2*fa3*fan 求求fi:i能变成其它数字的个数？能变成其它数字的个数？构造构造09十个点的图十个点的图i能到达哪些点？能到达哪些点？ /noip2001 const maxn=51; var a:array0.9,0.9 of boolean; f:array0.9 of integer; ans:array0.500 of shortint; s:string; n,len:integer; procedure init; var k,i,p,q:integer; begin fillchar(a,sizeof(a),false); for i:=0 t

42、o 9 do ai,i:=true; readln(s); readln(k); for i:=1 to k do begin readln(p,q); ap,q:=true; end; end;构图构图生产数组生产数组f procedure makef; var i,j,k:integer; begin for k:=0 to 9 do for i:=0 to 9 do for j:=0 to 9 do ai,j:=ai,jor(ai,k and ak,j); for i:=0 to 9 do for j:=0 to 9 do if ai,j then inc(fi); end; proce

43、dure mul(k:integer); /高精度乘单精度高精度乘单精度 var i,m:integer; begin len:=ans0; for i:=1 to len do ansi:=ansi*k; for i:=1 to len do begin ansi+1:=ansi+1+ansi div 10; ansi:=ansi mod 10; end; m:=anslen+1; while m0 do begin inc(len); anslen:=m mod 10; m:=m div 10; end; ans0:=len; end;main procedure main; var i,

44、k:integer; begin makef; n:=length(s); fillchar(ans,sizeof(ans),0); ans1:=1; ans0:=1; for i:=1 to n do begin k:=ford(si)-48; if k0 then mul(k); end; end; procedure print; var i:integer; begin for i:=ans0 downto 1 do write(ansi); writeln; end; begin init; main; print; end.引例引例：现在，我们想从城市现在，我们想从城市A A到达城

45、市到达城市E E。怎样走才能使得路径最短，最短路径的长度是多少？怎样走才能使得路径最短，最短路径的长度是多少？ 1234567891011531638438556343五、图的最短路径五、图的最短路径已知各个城市之间的道路情况如下：已知各个城市之间的道路情况如下：图中两点间的最短距离图中两点间的最短距离两类问题：两类问题：1、图中每对顶点（任意两点）之间的最短路径、图中每对顶点（任意两点）之间的最短路径 （弗洛伊德算法：（弗洛伊德算法：f loyed）。）。2、图中一个顶点到其他顶点的最短路径、图中一个顶点到其他顶点的最短路径 （迪杰斯特拉算法：（迪杰斯特拉算法：dijkstra）。）。一）、

46、计算每一对顶点间的最短路径（一）、计算每一对顶点间的最短路径（floyd算法）算法）目标：把图中任意两点目标：把图中任意两点i与与j之间的最短距离都求出来之间的最短距离都求出来 di,j。原理：根据图的传递闭包思想：原理：根据图的传递闭包思想：ijkif di,k+dk,jdi,j then di,j=di,k+dk,jfor 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;算法写法：算法写法：floyed2.pas初始化条件：初始化条件：D i, i =0 /自己到自己为

47、自己到自己为0；对角线为；对角线为0；Di,j=边权，边权，i与与j有直接相连的边有直接相连的边Di,j= + ，i与与j无直接相连的边。无直接相连的边。 / 一般设为：一般设为： maxint/2 or maxlongint/2;举例：举例： 已知下图中给定的关系，求出图中任意给定两点之间的最短距离已知下图中给定的关系，求出图中任意给定两点之间的最短距离123452317549137输入：输入：51 51 2 231 3 171 5 492 3 52 4 134 5 7要求：输出最短距离要求：输出最短距离d1,5。 / floyed2.pas分析：分析：Di,j:表示顶点表示顶点i到顶点到顶

48、点j之间的最短距离。之间的最短距离。初始化如下：初始化如下：0 23 17 49 23 0 5 13 17 5 0 13 0 749 7 01234523175491370 22 17 35 42 22 0 5 13 20 17 5 0 18 25 35 13 18 0 7 42 20 25 7 0 floyedprocedure 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 div 2; while not seekeof do beg

49、in 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,j2: 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 方法一：方法一：floyed3.pas设设 pathi

50、,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,j0 then begin dfs(i,pathi,j); write(j, ); end; end;iPathi,jj方法二：方法二：floyed4.pas设设 pathi,j 记录能使记录能使i到到j的距离

51、变短的结点。的距离变短的结点。初始化：初始化：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,j0 then begin dfs(i,pathi,j); write(pathi,j, ); dfs(pathi,j,j); end; end;输出输出i到到j的最短路径：

52、的最短路径：Write(i); dfs(i,j); write(j);在无向图中：在无向图中： 求求A到到B中间经过的最少结点？中间经过的最少结点？方法：方法：边权值设为边权值设为1 1，求，求A A到到B B的最短距离的最短距离d d。d-1d-1是中间经过的最少结点。是中间经过的最少结点。二）、计算某一顶点到其它所有顶点的最短路径二）、计算某一顶点到其它所有顶点的最短路径 （单源最短路径问题：（单源最短路径问题：dijkstra 算法）算法）开始点（源点）：开始点（源点）：startDi:顶点顶点i到到start的最短距离。的最短距离。初始：初始：Dstart=0；Di=astart,i

53、（无边设为（无边设为maxint）1253410757173449start其它其它n-1个点个点集合集合1：已求点：已求点集合集合2：未求点：未求点1、在集合、在集合2中找一个到中找一个到start距离最近的顶点距离最近的顶点k ，距离，距离=dk2、把顶点、把顶点k加到集合加到集合1中，同时修改集合中，同时修改集合2 中的剩余顶点中的剩余顶点j的的dj是否经过是否经过k后变短。如果变短修改后变短。如果变短修改djIf dk+ak,jdj then dj=dk+ak,j3、重复、重复1，直至集合，直至集合2空为止。空为止。125341075717344913顶点顶点12345FiTFFFFD

54、i010497Pathi11,21,31,5顶点顶点12345FiTFFFTDi0104920207Pathi11,21,31,5,41,5顶点顶点12345FiTTFFTDi0102717177Pathi11,21,2,31, 2,41,5511 2 101 5 72 3 172 4 72 5 53 4 344 5 13顶点12345FiTTTTTDi01027177Pathi11,21,2,31, 2,41,5顶点12345FiTTFTTDi01027177Pathi11,21,2,31, 2,41,5 for i:=1 to n do begin di:=astard,i; fi:=fa

55、lse; end; fstart:=true; / 加入集合加入集合1 for i:=2 to n do begin min:=maxint; k:=0; for j:=1 to n do if (not fj) and (djmin) then begin min:=dj; k:=j; end; if (k=mb) then exit; /找到目标找到目标 if (k=0)or(min=maxint) then exit; /更新结点求完了更新结点求完了 fk:=true; / 加入集合加入集合1 for j:=1 to n do /修改集合修改集合2中的中的dj if (not fj) a

56、nd (dk+ak,jdj) then dj:=dk+ak,j; end;dijkstra 算法算法Writeln(dstrat,mb) 时间：时间：O(n2)怎样输出路径？怎样输出路径？ for i:=1 to n do begin di:=as,i; pathi for i:=1 to n do begin di:=as,i; pathi:=s; end;:=s; end; ds:=0; fs:=true;paths ds:=0; fs:=true;paths:=0;:=0; for i:=2 to n do for i:=2 to n do begin begin min:=maxint

57、 min:=maxint; k:=0; k:=0; for j:=1 to n do / for j:=1 to n do /找距起点找距起点s s最近的点最近的点k k if (not fj) and (dj if (not fj) and (djmin) thenmin) then begin min:=dj begin min:=dj; k:=j; end; k:=j; end; if (k=t)or(min=maxint if (k=t)or(min=maxint) then break;) then break; fk fk:=true;:=true; for j:=1 to n d

58、o / for j:=1 to n do / 更新其他接点的更新其他接点的djdj if (not fj)and(dk+ak,jdj if (not fj)and(dk+ak,jdj) then) then begin dj:=dk+ak,j; pathj:=k;end begin dj:=dk+ak,j; pathj:=k;end; ; end; end; m:=0; i:=t; m:=0; i:=t; while i0 do while i0 do begin begin inc(m); waym inc(m); waym:=i;:=i; i:=pathi i:=pathi; end; e

59、nd; for i:=m downto 1 do write(wayi, );S：起点；：起点；t：终点；：终点；pathi：i的前驱结点；的前驱结点；way：从：从s到到t的结点路径的结点路径使用条件：使用条件： Floyed: 可以有负权，无负权回路。可以有负权，无负权回路。O(n3) Dijkstra: 不能有负权。不能有负权。O(n2)21534424-7421534424-34图图 1图图 2单源最短路径的单源最短路径的Bellman-ford算法算法 执行执行v-1次，每次对每条边进行松弛操作次，每次对每条边进行松弛操作 时间时间O（v*e） v:顶点；顶点；e：边：边swuvif

60、 disu+wdisv then disv:=disu+w;能判断有无负权回路能判断有无负权回路 type edge=record a,b,w :integer; end; var edges :array1.maxeof edge; /边 dis :array1.maxnof integer; /距源点s距离 pre :array1.maxnof integer; /前驱 e,n,s :integer;求最短路并判是否有负权回路求最短路并判是否有负权回路 function bellman_ford:boolean; var i,j :integer; begin for i:=1 to n-