《图及其应用》课件.ppt

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

1、第第15讲讲:数据结构之数据结构之 图图一、一、图的基本概念图的基本概念二、图的存储结构二、图的存储结构三、图的遍历三、图的遍历四、无向图的传递闭包四、无向图的传递闭包五、最短五、最短路径路径六、最小生成树六、最小生成树七、拓扑排序七、拓扑排序1、图的的定义、图的的定义 图是由顶点图是由顶点V V的集合和边的集合和边E E的集合组成的二元组：的集合组成的二元组：记记G=G=（V V，E E）存在一个结点存在一个结点v v，可能含有多个前驱结点和后继结点。，可能含有多个前驱结点和后继结点。一、一、图的基本概念图的基本概念1253412534无向图：无向图：在图在图G=G=（V V，E E）中，如

2、果对于任意的顶点）中，如果对于任意的顶点a a，bVbV，当当(a(a，b)Eb)E时，必有（时，必有（b b，a a）EE（即关系（即关系R R对称），此图称为对称），此图称为无向图。无向图。无向图中用不带箭头的边表示顶点的关系无向图中用不带箭头的边表示顶点的关系V=1,2,3,4,5E=(1,2),(1,3),(1,4),(2,3),(2,5),(3,5),(4,5)125342、无向图和有向图、无向图和有向图有向图：有向图：如果对于任意的顶点如果对于任意的顶点a a，bVbV，当，当(a(a，b)Eb)E时时 ，(b(b，a)Ea)E未未必成立，则称此图为有向图。必成立，则称此图为有向图

3、。在有向图中，通常用带箭头的边连接两个有关联的结点。在有向图中，通常用带箭头的边连接两个有关联的结点。V=1,2,3,4,5 V=1,2,3,4,5 E=,E=,12534在无向图中：顶点在无向图中：顶点v v的度是指与顶点的度是指与顶点v v相连的边的数目。相连的边的数目。D(2)=3D(2)=33 3、顶点的度、入度和出度、顶点的度、入度和出度在有向图中：在有向图中：入度入度以该顶点为终点的边的数目和以该顶点为终点的边的数目和.ID(3)=2 .ID(3)=2 出度出度以该顶点为起点的边的数目和以该顶点为起点的边的数目和.OD(3)=1.OD(3)=1度数为奇数的顶点叫做奇点，度数为偶数的

4、点叫做偶点。度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。度：等于该顶点的入度与出度之和。度：等于该顶点的入度与出度之和。D(5)=ID(5)+OD(5)=1+2=3D(5)=ID(5)+OD(5)=1+2=3 1253412534图中所有顶点的度图中所有顶点的度=边的两倍边的两倍图1图2完全图完全图4 4、路径、路径、简单路径、回路简单路径、回路 在在图图G=G=（V V，E E）中中，如如果果对对于于结结点点a a，b b，存存在在满满足足下下述述条条件件的的结结点点序序列列x x1 1xxk k(k1)(k1)x x1 1=a=a，x xk k=b =b (x(xi i，x xi+1

5、i+1)E i=1k-1E i=1k-1则则称称结结点点序序列列x x1 1=a=a，x x2 2，x xk k=b=b为为结结点点a a到到结结点点b b的的一一条条路路径径，而而路路径径上上边边的数目（的数目（k-1k-1）称为该路径的长度。）称为该路径的长度。1253412534图1图2图图1:1、(1,2,3,5)长度长度=32、(1,2,3,5,2)长度长度=43、(1,2,5,4,1)长度长度=4图图2:(1,2,5,4)长度长度=3（1）、如果一条路径上的结点除起点）、如果一条路径上的结点除起点x1和终点和终点xk可以相同外，其它结可以相同外，其它结点均不相同，则称此路径为一条简

6、单路径。点均不相同，则称此路径为一条简单路径。（2）、）、x1=xk的简单路径称为回路（也称为环）的简单路径称为回路（也称为环）5、连通、连通图、连通分量、连通、连通图、连通分量(无向图无向图)直观理解：直观理解：连通：连通：“连成一片连成一片”。连通图：连通图：“能连成一片的图能连成一片的图”。1253412534678图一图一图二图二确切定义：确切定义：连通连通：如果从顶点：如果从顶点u u到到v v有路径，则称有路径，则称u u和和v v是连通的。是连通的。连通图连通图：图中任意的两个顶点：图中任意的两个顶点u u和和v v都是连通的。都是连通的。图一是连通图，图二是非连通图图一是连通图

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

8、25342342132二、图的存储结构二、图的存储结构1 1、邻接矩阵（静态数组）、邻接矩阵（静态数组）2 2、邻接表（指针数组）、邻接表（指针数组）3 3、边集数组、边集数组4 4、十字链表、十字链表5 5、邻接多重表、邻接多重表图的邻接矩阵表示法图的邻接矩阵表示法 邻邻接接矩矩阵阵是是表表示示结结点点间间相相邻邻关关系系的的矩矩阵阵。若若G=G=（V V，E E）是是一一个个具具有有n n个个结结点点的的图图，则则G G的的邻邻接接矩矩阵阵是是如如下下定定义义的的二二维维数数组组a a。1、邻接矩阵、邻接矩阵ai,j=1(或权值或权值)：无向图：有边：无向图：有边(i,j)和边和边(j,i

9、)有向图：有边有向图：有边0:i到到j无边无边1253401110101011100110001011101234512345125342342132022302010321002300040324012345123451253401010001011000000000001101234512345对角线为对角线为0：自身不相连。：自身不相连。无向图：是对称矩阵。有向图一般不是。无向图：是对称矩阵。有向图一般不是。第第i行非行非0的个数是结点的个数是结点i的度的度具体到题目时，数据的给出格式多种多样：具体到题目时，数据的给出格式多种多样：1）、直接给出邻接矩阵，直接读即可。）、直接给出邻接矩阵

10、，直接读即可。如：如：输入文件内容：输入文件内容：50223020103210023000403240Maxn=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）、给出边的顶点。）、给出边的顶点。如输入文件：两个顶点及权值如输入文件：两个顶点及权值57122132143231253352454125342342132Readln(n);readln(m);Fork:=1tomdobeginre

11、adln(I,j,x);aI,j:=x;aj,i:=x;end2、邻接表、邻接表:方法方法1125342342132123452232431231531221521354233244头指针头指针邻接点指针邻接点指针结点邻接点指针邻接点边权值下一个邻接点指针typeedge=node;node=recorddata:integer;weight:integer;next:edge;end;vpoint=recorddata:integer;link:edge;end;vara:array1.maxnofvpoint;/具体操作：具体操作：datalinkdataweightnext邻接表方法邻接

12、表方法2：1234523413512515234125342342132权值单独用另外的数组权值单独用另外的数组W设置结点指针设置结点指针结点邻接点指针typepoint=node;node=recorddata:integer;next:point;end;vara:array1.maxvofpoint;/具体操作：具体操作：datanext三、图的遍历三、图的遍历 给出一个图给出一个图G G，从某一个初始点出发，按照一定的搜索方法对图，从某一个初始点出发，按照一定的搜索方法对图中的每一个结点访问仅且访问一次的过程。中的每一个结点访问仅且访问一次的过程。访问结点：处理结点的过程。如输出结点的

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

14、始点出发继续作为初始点出发继续深搜。深搜。当当i i的所有邻接点都被访问完，则退回到的所有邻接点都被访问完，则退回到i i的父结点的另一个邻的父结点的另一个邻接点接点k k再继续深搜。再继续深搜。直到全部接点访问完毕直到全部接点访问完毕14356782910proceduredfs(k:integer);/从从k点出发遍历点出发遍历varj:integer;/局部变量？局部变量？beginwrite(k,);fk:=true;forj:=1tondoif(fj=false)and(ak,j=1)thendfs(j);end;/读入边的关系读入边的关系readln(n);readln(m);fo

15、ri:=1tomdobeginreadln(x,y);ax,y:=1;ay,x:=1;end;上图的遍历结果：上图的遍历结果：Dfs(1)?proceduremain;vari:integer;beginfillchar(f,sizeof(f),false);fori:=1tondoifnotfithendfs(i);end;2 2、广度优先搜索、广度优先搜索(宽度优先搜索）宽度优先搜索）BFSBFS 广度优先搜索广度优先搜索按层次按层次遍历的过程，其搜索过程如下：遍历的过程，其搜索过程如下：假假设设从从图图中中某某结结点点i i出出发发，在在访访问问了了i i之之后后依依次次访访问问i i的

16、的各各个个未未曾曾访访问问的的邻邻接接点点，然然后后分分别别从从这这些些邻邻接接点点出出发发按按广广度度优优先先搜搜索索的的顺顺序遍历图，直至图中所有可被访问的结点都被访问到。序遍历图，直至图中所有可被访问的结点都被访问到。14356782910procedurebfs(i:integer);/varj,k:integer;beginfillchar(q,sizeof(q),0);open:=0;closed:=1;q1:=i;write(i,);fi:=true;whileopencloseddobegininc(open);k:=qopen;forj:=1tondoif(ak,j=1)an

17、d(fj=false)thenbeginwrite(j,);fj:=true;inc(closed);qclosed:=j;end;end;end;3、图的遍历的简单应用、图的遍历的简单应用1 1、犯罪团伙、犯罪团伙 警察抓到了警察抓到了n n个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知道其中的一些罪犯之间相不能判断有多少个团伙，但通过警察的审讯，知道其中的一些罪犯之间相互认识，已知同一犯罪团伙的成员之间直接或间接认识。有可能一个犯罪互认识，已知同一犯罪团伙的成员之间直接或间接认识。有可能一个犯罪

18、团伙只有一个人。请你根据已知罪犯之间的关系，确定犯罪团伙的数量。团伙只有一个人。请你根据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编号从已知罪犯的编号从1 1至至n n。输入：输入：第一行：第一行：n n（=1000,=1000,罪犯数量），罪犯数量），第二行：第二行：m m（50005000，关系数量），关系数量）以下若干行：每行两个数：以下若干行：每行两个数：I I 和和j j，中间一个空格隔开，表示罪犯，中间一个空格隔开，表示罪犯i i和罪犯和罪犯j j相互认识。相互认识。输出：输出：一个整数，犯罪团伙的数量。一个整数，犯罪团伙的数量。样例输入：11 8 1 24 35 41 3

19、5 67 105 108 9输出：3说明：共三个犯罪团伙。把把n个人看成图的个人看成图的n个顶点；相互认识的连一条边。个顶点；相互认识的连一条边。相互认识的所有人构成一个极大连通子图。相互认识的所有人构成一个极大连通子图。问题转化为：问题转化为：求无向图的连通分量求无向图的连通分量（有多少个极大连通子图）（有多少个极大连通子图）proceduremain;vari:integer;beginsum:=0;fillchar(f,sizeof(f),false);fori:=1tondoifnotfithenbegininc(sum);dfs(i);end;writeln(sum);end;123

20、54672、邮递员邮递员 邮递员在送信时，为了节省路途，自己规定：每次总是从n个村子中选择其中一个合适的村子出发，途中每个村子仅且经过一次，送完所有的信。已知各个村子的道路连通情况。请你帮邮递员选择一条合适的路线。输入：第一行：整数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

21、1 0输出：2 3 7 6 5 1 4分析：分析：邮递员从某一个村子邮递员从某一个村子A出发；每个村子访问仅且访问一次，最后到达出发；每个村子访问仅且访问一次，最后到达村子村子B结束，从结束，从A到到B的路线成为的路线成为哈密顿路哈密顿路。如果如果A和和B重合，即回到出发点，称为重合，即回到出发点，称为哈密顿回路哈密顿回路。b:array1.maxnofinteger;/记录哈密顿路记录哈密顿路proceduremain;vari:integer;beginfori:=1tondobeginfillchar(visited,sizeof(visited),false);b1:=i;visite

22、di:=true;dfs(i,1);end;print(0);end;proceduredfs(i,k:integer);/当前已找到有当前已找到有k个点，要搜第个点，要搜第k+1个点个点varj:integer;beginifk=nthenprint(1);forj:=1tondoif(aj,i=1)and(visitedj=false)thenbeginvisitedj:=true;bk+1:=j;/找到第找到第k+1个点并记下个点并记下dfs(j,k+1);visitedj:=false;/回溯回溯end;end;怎样求哈密顿回路？怎样求哈密顿回路？3 3、安排座位、安排座位 n n个个

23、客客人人围围着着一一个个桌桌子子吃吃饭饭，每每一一个个人人都都至至少少认认识识其其他他的的2 2个个客客人人。请请设设计计程程序序求得求得n n个人的一种坐法，使得每个人都认识他左右的客人。个人的一种坐法，使得每个人都认识他左右的客人。输入输入:第一行第一行:n:n（吃饭人的个数）。（吃饭人的个数）。以下以下n n行：第行：第i i行的第一个数行的第一个数k k表示第表示第i i个人认识的人数，后面个人认识的人数，后面k k个数依次为个数依次为i i认识的认识的人的编号。人的编号。输出：所有座法，要求第一个人为输出：所有座法，要求第一个人为1 1号作为起点，按顺时针输出其它人的编号。号作为起点

24、，按顺时针输出其它人的编号。样例输入：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 34 4、素数链、素数链设计程序将设计程序将1 1。n n（2020）排成一排，使任意两个相邻的数的和为素数。）排成一排，使任意两个相邻的数的和为素数。第第1 1个和最后一个的和也为素数个和最后一个的和也为素数.输出输出:第一个数为第一个数为1.1.四、无向图的传递闭包四、无向图的传递闭包判断无向图的连通性判断无向图的连通性1234657输入图的边的信息，输出输入图的边的信息，

25、输出各点的连通行。各点的连通行。输入：输入：7122313345667输出：输出：11110001111000111100011110000000111000011100001110110000101000011010000010000000001000001010000010邻接矩阵邻接矩阵判断结点判断结点i和和j的连通性：的连通性：ijk1、结点、结点i和和j如果原来有边则连通。如果原来有边则连通。2、如果、如果i和和j之间没有边：之间没有边：如果存在另外的一个结点如果存在另外的一个结点k，满足：，满足：i与与k连通，连通，k与与j连通，则连通，则i与与j连通。连通。否则否则i和和j不连通

26、。不连通。Cani,j:true，i与与j之间有边；之间有边；false：无边。：无边。则：则：Cani,j=cani,jor(cani,kandcank,j)fork:=1tondofori:=1tondoforj:=1tondocani,j:=cani,jor(cani,kandcank,j);过程：过程：产生数产生数【问题描述【问题描述:】给出一个正整数给出一个正整数n（n1050)和和k个变换规则（个变换规则（k536上面的整数上面的整数234经过变换后可能产生出的整数为（包括原数）经过变换后可能产生出的整数为（包括原数）:234534264564共共4种不同的产生数。种不同的产生数。

27、【任务：】【任务：】给出一个整数给出一个整数n和和k个变换规则。个变换规则。求经过任意次的变换（求经过任意次的变换（0次或多次），能产生出多少个不同整数。仅要求输出个数。次或多次），能产生出多少个不同整数。仅要求输出个数。【输入：】【输入：】第一行：第一行：n。第二行：。第二行：k。以下。以下k行：每行两个一位数：行：每行两个一位数：xy，中间一个空格，表示一个，中间一个空格，表示一个变换规则：变换规则：x可以变为可以变为y。【输出：】【输出：】一个整数（满足条件的个数）：一个整数（满足条件的个数）：【输入样例：】【输入样例：】23422536【样例输出：】【样例输出：】4应用举例应用举例本题

28、搜索显然是不行的。本题搜索显然是不行的。对于只需计数而不需求具体方案的题目，一般都不会用搜索解决。对于只需计数而不需求具体方案的题目，一般都不会用搜索解决。分析：分析：乘法原理直接进行计数。乘法原理直接进行计数。用用Fi表示数字表示数字i包括本身可以变成的数字总个数包括本身可以变成的数字总个数这里的变成可以是直接变成也可以是间接变成：这里的变成可以是直接变成也可以是间接变成：比如比如3-5,5-7,那么那么3-7那么对于一个数那么对于一个数a（用数组存（用数组存,长度为长度为n），根据乘法原理它能产生出），根据乘法原理它能产生出不同整数数量：不同整数数量：Fa1*Fa2*Fa3*Fan引例引例

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

30、迪杰斯特拉算法：dijkstra）。）。一）、计算每一对顶点间的最短路径（一）、计算每一对顶点间的最短路径（floyd算法）算法）目标：把图中任意两点目标：把图中任意两点i与与j之间的最短距离都求出来之间的最短距离都求出来dI,j。原理：根据图的传递闭包思想：原理：根据图的传递闭包思想：ijkifdI,k+dk,jdI,jthendI,j=dI,k+dk,jfork:=1tondofori:=1tondoforj:=1tondoifdi,k+dk,jdi,jthendi,j:=di,k+dk,j;算法写法算法写法1：初始化条件：初始化条件：Di,i=0/自己到自己为自己到自己为0；对角线为；对

31、角线为0；DI,j=边权，边权，i与与j有直接相连的边有直接相连的边DI,j=+，i与与j无直接相无直接相连连的的边边。/一般一般设为设为：maxintormaxlongint;举例：举例：已知下图中给定的关系，求出图中任意给定两点之间的最短距离已知下图中给定的关系，求出图中任意给定两点之间的最短距离123452317549137输入：输入：5151223131715492352413457要求：输出最短距离要求：输出最短距离d1,5。分析：分析：DI,j:表示顶点表示顶点i到顶点到顶点j之间的最短距离。之间的最短距离。初始化如下：初始化如下：0231723051517501307497012

32、345231754913702217354222051320175018253513180742202570floyedprocedureinit;readln(n);readln(p,q);fori:=1tondoforj:=1tondoifi=jthendi,j:=0elsedi,j:=maxint;whilenotseekeofdobeginreadln(i,j,w);di,j:=w;dj,i:=w;end;procedurefloyed;beginfork:=1tondofori:=1tondoforj:=1tondoifdi,k+dk,jdi,jthendi,j:=di,k+dk,j

33、;end;procedureprint;beginwriteln(dp,q);end;算法写法算法写法2：02317002305150175000013007490070初始化：无边的全都为初始化：无边的全都为0procedureinit;fillchar(d,sizeof(d),0);readln(n);readln(p,q);whilenotseekeofdobeginreadln(i,j,w);di,j:=w;dj,i:=w;end;/floyedfork:=1tondofori:=1tondoif(ki)and(di,k0)thenforj:=1tondoif(kj)and(ij)an

34、d(dk,j0)thenif(di,j=0)or(di,k+dk,j2:22:1321-3:17:131-4:35:13241-5:42:132452-3:5:232-4:13:242-5:20:2453-4:18:3243-5:25:32454-5:7:45方法一：方法一：设设pathI,j记录记录i到到j的最短路径中的最短路径中j的前驱顶点。的前驱顶点。如样例：如样例：1-4:35:1324path1,4=2path1,2=3path1,3=1初始化：初始化：i到到j有边，则有边，则pathI,j:=I;pathj,i:=jfork:=1tondofori:=1tondoforj:=1to

35、ndoifdi,k+dk,j0thenbegindfs(i,pathi,j);write(j,);end;end;iPathI,jj方法二：方法二：设设pathI,j记录能使记录能使i到到j的距离变短的结点。的距离变短的结点。初始化：初始化：pathI,j=-1:i与与j不通的不通的pathI,j:=0;从从i到到j的最短路径是直接到达的。开始有边的都直接到达。的最短路径是直接到达的。开始有边的都直接到达。PathI,j0;从从i到到j的最短路径要经过点的最短路径要经过点pathI,j.fork:=1tondofori:=1tondoforj:=1tondoifdi,k+dk,j0thenbe

36、gindfs(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）二）、计算某一顶点到其它所有顶点的最短路径二）、计算某一顶点到其它所有顶点的最短路径（单源最短路径问题：（单源最短路径问题：dijkstra算法）算法）开始点（源点）：开始点（

37、源点）：startDi:顶点到顶点到st的最短距离。的最短距离。初始：初始：Dstart=0；Di=ast,istart其它其它n-1个点个点集合集合1：已求点：已求点集合集合2：未求点：未求点1、在集合、在集合2中找一个到中找一个到start距离最近的顶点距离最近的顶点k，距离，距离=dk2、把顶点、把顶点k加到集合加到集合1中，同时修改集合中，同时修改集合2中的剩余顶点中的剩余顶点j的的dj是否经过是否经过k后变短。如果变短修改后变短。如果变短修改djIfdk+ak,jdjthendj=dk+ak,j3、重复、重复1，直至集合，直至集合2空为止。空为止。fori:=1tondobegind

38、i:=astart,i;fi:=false;end;fstart:=true;/加入集合加入集合1fori:=2tondobeginmin:=maxint;forj:=1tondoif(notfj)and(djmin)thenbeginmin:=dj;k:=j;end;fk:=true;/加入集合加入集合1forj:=1tondo/修改集合修改集合2中的中的djif(notfj)and(dk+ak,j2:22:1321-3:17:131-4:35:13241-5:42:13245怎样输出路径？怎样输出路径？六、图的最小生成树六、图的最小生成树普里姆算法（普里姆算法（prim）克鲁斯卡尔（克鲁斯

39、卡尔（kruskal）网络建设网络建设【问题描述：】【问题描述：】OI国由国由n个城市组成，所有城市位于一平面坐标系中，每个城市的坐标是已知个城市组成，所有城市位于一平面坐标系中，每个城市的坐标是已知的，且坐标都是整数。现在，的，且坐标都是整数。现在，OI国的国的CHEN主席想加快网络信息传递，决定选主席想加快网络信息传递，决定选若干对城市，每对城市之间用一条高速网线相连，并且使所有的城市都可以直若干对城市，每对城市之间用一条高速网线相连，并且使所有的城市都可以直接或间接相连。已知两城市之间的距离为它们的直线距离，求所需网线的最小接或间接相连。已知两城市之间的距离为它们的直线距离，求所需网线的

40、最小长度。长度。【输入：】【输入：】nn行，每行有两个整数行，每行有两个整数x,y表示第表示第i个城市的坐标为个城市的坐标为(x,y)【输出：】【输出：】最短的网线的长度。最短的网线的长度。结果保留结果保留3为小数。为小数。【输入样例：】【输入样例：】6214154353323【输出样例：】【输出样例：】数据规模数据规模n=5001=x,y=1000012345621345612435173010247235最小生成树：最小生成树：含有含有n个结点的图，从中选个结点的图，从中选n-1条边，保持条边，保持n个点个点中任意两点是连通的，并且中任意两点是连通的，并且n-1条边的和最小。这条边的和最小

41、。这n个个点和这点和这n-1条边就成为原图的最小生成树。条边就成为原图的最小生成树。任意结点开始（不妨设为任意结点开始（不妨设为v1）构造最小生成树：）构造最小生成树：首先把这个结点包括进生成树里，然后在那些其一个端首先把这个结点包括进生成树里，然后在那些其一个端点已在生成树里、另一端点还未在生成树里的所有边中点已在生成树里、另一端点还未在生成树里的所有边中找出权最小的一条边，并把这条边、包括不在生成树的找出权最小的一条边，并把这条边、包括不在生成树的另一端点包括进生成树，另一端点包括进生成树，。依次类推，直至将所有结。依次类推，直至将所有结点都包括进生成树为止。点都包括进生成树为止。普里姆算

42、法（普里姆算法（prim）1243517301024723512345fori:=1tondobegindi:=a1,i;fi:=false;end;f1:=true;/放在生成树中放在生成树中ans:=0;fori:=2tondobeginmin:=maxint;forj:=1tondoif(notfj)and(djmin)thenbeginmin:=dj;k:=j;end;inc(ans,dk);fk:=true;forj:=1tondoif(notfj)and(ak,jdj)thendj:=ak,j;end;Prim算法描述：算法描述：/ai，j：i到到j的边长。的边长。/Di：结点：结

43、点i到生成树中结点的最短距离到生成树中结点的最短距离/fi:true:在生成树种，在生成树种，false：不在生成树中。：不在生成树中。输入：输入：51223131715492352413457输出最小生成树的边：输出最小生成树的边：pre:array1.maxnofinteger;prei:点点i的前驱点的前驱点tree:array1.maxn-1,1.2ofinteger;记录边记录边fori:=1tondobegindi:=a1,i;prei:=1;fi:=false;end;f1:=true;ans:=0;fori:=1ton-1dobeginmin:=maxint;forj:=1to

44、ndoif(notfj)and(djmin)thenbeginmin:=dj;k:=j;end;treei,1:=k;treei,2:=prek;inc(ans,dk);fk:=true;forj:=1tondoif(notfj)and(ak,jdj)thenbegindj:=ak,j;prej:=k;end;end;克鲁斯卡尔（克鲁斯卡尔（kruskal）算法步骤：算法步骤：1、把图中的边按权值从小到大排序。、把图中的边按权值从小到大排序。2、按从小到大的顺序依次向树中加边。、按从小到大的顺序依次向树中加边。在添加每一条边（在添加每一条边（u，v）时，如果）时，如果u和和V两个点都已在树中，

45、一旦两个点都已在树中，一旦添加，就回构成回路，所以放弃该边，在向后找下一条边。添加，就回构成回路，所以放弃该边，在向后找下一条边。3、直到添加、直到添加n-1条边。条边。关键：加边时不能构成回路：边的两个顶点是否已在树种。关键：加边时不能构成回路：边的两个顶点是否已在树种。1243517301024723512345typenode=recorddata:integer;u,v:integer;end;vare:array1.maxn*(maxn-1)div2ofnode;/边边f:array1.maxnofinteger;/父亲接点父亲接点n,m:integer;ans:integer;re

46、adln(n);m:=0;whilenotseekeofdobeginreadln(i,j,k);inc(m);em.data:=k;em.u:=i;em.v:=j;end;procedurekruskal;vari:integer;beginsort;fori:=1tondofi:=0;/初始化根为初始化根为0ans:=0;fori:=1tomdounion(ei);end;procedureunion(p:node);/检查边检查边p是否能加到生成树中是否能加到生成树中varx,y:integer;beginx:=);/找找u的根的根y:=);/找找v的根的根ifxythen/不同根，构不

47、成环，加入不同根，构不成环，加入begin);fy:=x;/根合并根合并end;end;functionfind(i:integer):integer;/查找查找i的父亲的父亲beginiffi=0thenexit(i);/i是根是根ifffi=0thenexit(fi);/i的父亲是根的父亲是根find:=find(fi);/递归查找递归查找fi:=find;/路径压缩路径压缩end;七、拓扑排序七、拓扑排序有有n个士兵个士兵(1n100)，编号依次为，编号依次为1、2、3、。队列训练时，指。队列训练时，指挥官要把一些士兵从高到矮依次排成一行。但现在指挥官不能直接获得每挥官要把一些士兵从高到

48、矮依次排成一行。但现在指挥官不能直接获得每个人的身高信息，只能获得个人的身高信息，只能获得“p1比比p2高高”这样的比较结果。这样的比较结果。请按照从高到低输出一种合理的排队序列。请按照从高到低输出一种合理的排队序列。士兵排队士兵排队21456378输入：输入：821141545463537565878输出：输出：21347568拓扑序列的计算：拓扑序列的计算：从图中选择一个入度为从图中选择一个入度为0的结点且输出之；的结点且输出之；从图中删除该结点及其所有出边从图中删除该结点及其所有出边（即与之相邻的所有结点的入度减一）；（即与之相邻的所有结点的入度减一）；反复执行这两个步骤，直至所有结点都

49、输出了，也就是整个拓扑排序完反复执行这两个步骤，直至所有结点都输出了，也就是整个拓扑排序完成了。成了。对于给定的有向图，找出一个包含所有顶点的序列，并且顶点的先后对于给定的有向图，找出一个包含所有顶点的序列，并且顶点的先后关系不变，这个序列称为原图的一个拓扑序列。生成拓扑序列的过程叫拓关系不变，这个序列称为原图的一个拓扑序列。生成拓扑序列的过程叫拓扑排序。扑排序。注意：注意：1、有向图的拓扑序列不唯一。、有向图的拓扑序列不唯一。2、如果图中存在环，无拓扑序列。、如果图中存在环，无拓扑序列。a:array1.maxn,1.maxnofboolean;/边边ind：array1.maxnofint

50、eger;/顶点的入度顶点的入度top:array1.maxnofinteger;/拓扑序列拓扑序列n:integer;procedureinit;vari,j:integer;beginreadln(n);whilenotseekeofdobeginreadln(i,j);ai,j:=true;inc(indj);end;end;proceduretoposort;vari,j,k:integer;beginfori:=1tondobegink:=find;ifk=0thenprint(-1);topi:=k;indk:=-1;forj:=1tondoifak,jthendec(indj);