图及其基本算法幻灯片.ppt

《图及其基本算法幻灯片.ppt》由会员分享，可在线阅读，更多相关《图及其基本算法幻灯片.ppt（83页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图及其基本算法第1页，共83页，编辑于2022年，星期五图的概念图的概念图（图（graph）是图型结构的简称。它是一种复杂的非线性）是图型结构的简称。它是一种复杂的非线性数据结构。图在各个领域都着广泛的应用。图的二元组定数据结构。图在各个领域都着广泛的应用。图的二元组定义为：义为：G=（V,E）其中其中V是非空的顶点集合，即是非空的顶点集合，即 V=vi|1=i=1,vi elemtype，n 为为顶点数顶点数 E是是V上顶点的序偶或无序对的集合，即对应边上顶点的序偶或无序对的集合，即对应边的集合。的集合。第2页，共83页，编辑于2022年，星期五123412453图1 有向图图2 无向图第3

2、页，共83页，编辑于2022年，星期五图的基本术语图的基本术语 1、端点和邻接点、端点和邻接点 在一个无向图中，若存在一条边在一个无向图中，若存在一条边（vi，vj），则称），则称vi,vj为此边的两个端点，并称它们互为邻接点（为此边的两个端点，并称它们互为邻接点（adjacent），），即即vi是是vj的一个邻接点，的一个邻接点，vj也是也是vi的一个邻接点。的一个邻接点。在一个有向图中，若存在一条边在一个有向图中，若存在一条边，则称此边，则称此边是顶点是顶点vi的一条出边（的一条出边（outedge），顶点），顶点vj的一条入边的一条入边（inedge）；）；称称Vi为此边的起始端点，简称

3、起点或为此边的起始端点，简称起点或始点，始点，vj为此边的终止端点，简称终点；称为此边的终止端点，简称终点；称vi和和vj互为邻互为邻接点，并称接点，并称vj是是vi的出边邻接点，的出边邻接点，vi是是vj的入边邻接点。的入边邻接点。第4页，共83页，编辑于2022年，星期五 2、顶点的度、入度、出度顶点的度、入度、出度 无向图顶点无向图顶点v的度（的度（degree）定义为以）定义为以该顶点为一个端点的边的数目，简单地说，该顶点为一个端点的边的数目，简单地说，就是该顶点的边的数目，记为就是该顶点的边的数目，记为D（v）。如图）。如图2中中v1顶点的度为顶点的度为2，v2顶点的度为顶点的度为3

4、。有向。有向图中顶点图中顶点v的度有入度和出度之分，入度的度有入度和出度之分，入度（indegree）是该顶点的入边的数目，记为）是该顶点的入边的数目，记为ID（v）；出度（）；出度（outdegree）是该顶点的）是该顶点的出边的数目，记为出边的数目，记为OD（v）顶点）顶点v的度等于的度等于它的入度和出度之和，即它的入度和出度之和，即D（v）=ID（v）+OD（v）。）。第5页，共83页，编辑于2022年，星期五 3、完全图、稠密图、稀疏图、完全图、稠密图、稀疏图 若无向图中的每两个顶点之间都存在着若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存在一条边，有向图中的每

5、两个顶点之间都存在着方向相反的两条边，则称此图为完全图。着方向相反的两条边，则称此图为完全图。显然，若完全图是无向的，则图中包含有显然，若完全图是无向的，则图中包含有n（n-1）/2条边条边,若完全图是有向的，则图若完全图是有向的，则图中包含有中包含有n（n-1）条边。当一个图接近完全）条边。当一个图接近完全图时，则可称为稠密图，相反地，当一个图图时，则可称为稠密图，相反地，当一个图有较少的边数（即有较少的边数（即e n（n 1）时，则）时，则可称为稀疏图。可称为稀疏图。第6页，共83页，编辑于2022年，星期五12543G112543G212543G3第7页，共83页，编辑于2022年，星期

6、五 4、子图子图 设有两个图设有两个图G=（V,E）和）和G （V,E）,若若V是是V的子集，且的子集，且E是是E的子集，则的子集，则称称G是是G的子图。的子图。12453124531245图图的子图第8页，共83页，编辑于2022年，星期五5、路径和回路、路径和回路 在一个图在一个图G中，从顶点中，从顶点v到顶点到顶点v的一条路径的一条路径（path）是一个顶点序列）是一个顶点序列vi0,vi1,vi2,.,vim,其中其中v=vi0,v=vim,若此图是无向图，则（若此图是无向图，则（vi,j-1,vij）E（G），（），（1jm）；若此图是有向图，则）；若此图是有向图，则E（G），（），

7、（1jm）。路径长度是指该路径）。路径长度是指该路径上经过的边的数目。若一条路径上除了前后端点可以上经过的边的数目。若一条路径上除了前后端点可以相同外，所有顶点均不同，则称此路径为简单路径。相同外，所有顶点均不同，则称此路径为简单路径。若一条路径上的前后两端点相同，则被称为回路或环若一条路径上的前后两端点相同，则被称为回路或环（cycle），前后两端点相同的简单路径被称为简单），前后两端点相同的简单路径被称为简单回路或简单环回路或简单环。第9页，共83页，编辑于2022年，星期五6、连通和连通分量、连通和连通分量 在无向图在无向图G中，若从顶点中，若从顶点vi到顶点到顶点vj有路径，则称有路径

8、，则称vi和和vj是连通的。若图是连通的。若图G中任中任意两个顶点都连通，则称意两个顶点都连通，则称G为连通图，否为连通图，否则称为非连通图。无向图则称为非连通图。无向图G的极大连通子的极大连通子图称为图称为G的连通分量。显然，任何连通图的连通分量。显然，任何连通图的连通分量只有一个，即本身，而非连通的连通分量只有一个，即本身，而非连通图有多个连通分量。图有多个连通分量。第10页，共83页，编辑于2022年，星期五1254376G11254G1136G127G13第11页，共83页，编辑于2022年，星期五7、强连通图和强连通分量、强连通图和强连通分量 在有向图在有向图G中，若从顶点中，若从顶

9、点vi到顶点到顶点vj有有路径，则称从路径，则称从vi到到vj是连通的。若图是连通的。若图G中的中的任意两个顶点任意两个顶点vi和和vj都连通，即从都连通，即从vi到到vj和和从从vj到到vi都存在路径，则称都存在路径，则称G是强连通图。是强连通图。有向图有向图G的极大强连通子图称为的极大强连通子图称为G的强连通的强连通分量。显然，强连通图只有一个强连通分分量。显然，强连通图只有一个强连通分量，即本身，非强连通图有多个强连通分量，即本身，非强连通图有多个强连通分量。量。第12页，共83页，编辑于2022年，星期五12543G112543G2125G2143G22第13页，共83页，编辑于202

10、2年，星期五8、权和网、权和网 在一个图中每条边可以标上具有某种在一个图中每条边可以标上具有某种含义的数值，此数值称为该边的权含义的数值，此数值称为该边的权（weight）。例如，对于一个反映城市交）。例如，对于一个反映城市交通线路的图，边上的权可表示该条线路的长通线路的图，边上的权可表示该条线路的长度或等级；对于一个反映电子线路的图，边度或等级；对于一个反映电子线路的图，边上的权可表示两端点间的电阻、电流或电压；上的权可表示两端点间的电阻、电流或电压；对于一个反映零件装配的图，边上的权可表对于一个反映零件装配的图，边上的权可表示一个端点需要装配另一个端点的零件的数示一个端点需要装配另一个端点

11、的零件的数量；对于一个反映工程进度的图，边上的权量；对于一个反映工程进度的图，边上的权可表示从前一子工程到后一子工程所需要的可表示从前一子工程到后一子工程所需要的天数。边上带有权的图称作带权图，也常称天数。边上带有权的图称作带权图，也常称作网（作网（network）。）。第14页，共83页，编辑于2022年，星期五 图的存储结构图的存储结构 1、邻接矩阵邻接矩阵 邻接矩阵（邻接矩阵（adjacency matrix）是表示顶点之间相邻关）是表示顶点之间相邻关系的矩阵。设系的矩阵。设G（V，E）是具有）是具有n个顶点的图，顶点个顶点的图，顶点序号依次为序号依次为1、2、n，则，则G的邻接矩阵是具

12、有的邻接矩阵是具有如下定义的如下定义的n阶方阵。阶方阵。第15页，共83页，编辑于2022年，星期五邻接矩阵的表示1234有向图12453无向图第16页，共83页，编辑于2022年，星期五2、邻接表邻接表 邻接表（邻接表（adjacency list）是对图中的）是对图中的每个顶点建立一个邻接关系的单链表，并把每个顶点建立一个邻接关系的单链表，并把它们的表头指针用向量存储的一种图的表示它们的表头指针用向量存储的一种图的表示方法。为顶点方法。为顶点vi建立的邻接关系的单链表又建立的邻接关系的单链表又称作称作vi的邻接表。的邻接表。vi邻接表中的每个结点用邻接表中的每个结点用来存储以该顶点为端点或

13、起点的一条边的信来存储以该顶点为端点或起点的一条边的信息，因而被称为边结点。息，因而被称为边结点。vi邻接表中的结点邻接表中的结点数，对于无向图来说，等于数，对于无向图来说，等于vi的边数，邻接的边数，邻接点数或度数；对于有向图来说，等于点数或度数；对于有向图来说，等于vi的出的出边数、出边邻接点数或出度数。边数、出边邻接点数或出度数。第17页，共83页，编辑于2022年，星期五邻接表描述边结点：Eptr=enode;Eode=record adjvex:1.n;w:wtype;next:eptr end;vexnode=record data:datatype link:eptr;end;A

14、djlnk=array1.n of vexnode;Proc create(G)For i:=1 to n do begin input(gi.data);gi.link:=nil;end;For k:=1 to e do begin input(i,j);new(s);s.adjvex:=j;s.next:=gi.link;gi.link:=s;end;第18页，共83页，编辑于2022年，星期五1234有向图12342341有向图邻接表12453无向图4253543132123512无向图邻接表4第19页，共83页，编辑于2022年，星期五3、边集数组边集数组 边集数组（边集数组（edge

15、set array）是利用一维）是利用一维数组存储图中所有边的一种图的表示方法。数组存储图中所有边的一种图的表示方法。该数组中所含元素的个数要大于等于图中边该数组中所含元素的个数要大于等于图中边的条数，每个元素用来存储一条边的起点、的条数，每个元素用来存储一条边的起点、终点（对于无向图，可选定边的任一端点为终点（对于无向图，可选定边的任一端点为起点或终点）和权（若有的话），下各边在起点或终点）和权（若有的话），下各边在数组中的次序可任意安排，也可根据具体要数组中的次序可任意安排，也可根据具体要求而定。求而定。第20页，共83页，编辑于2022年，星期五 图的遍历图的遍历 1、深度优先遍历深度优

16、先遍历 深度优先搜索（深度优先搜索（depth first search）遍历类似树的先根遍历，它是一个递归过程）遍历类似树的先根遍历，它是一个递归过程.可叙述为：首先访问一个顶点可叙述为：首先访问一个顶点vi（开始为初始点），并将其标记为已访问过，然后从（开始为初始点），并将其标记为已访问过，然后从vi的一的一个未被访问的邻接点（无向图）或出边邻接点（有向图）出发进行深度优先搜索遍历，当个未被访问的邻接点（无向图）或出边邻接点（有向图）出发进行深度优先搜索遍历，当vi的所有邻接点均被访问过时，则退回到上一个顶点的所有邻接点均被访问过时，则退回到上一个顶点vk，从，从vk的另一个未被访问过的邻

17、接点出的另一个未被访问过的邻接点出发进行深度优先搜索遍历。发进行深度优先搜索遍历。算法：算法：proc dfs(v)beign print(v);visitedv:=true;for j:=1 to n do if not visitedj and gv,j=1 then dfs(j);end第21页，共83页，编辑于2022年，星期五练习1：无向图的深度优先搜索【问题描述】从文件中读入无向图的信息，按深度优先搜索的方式遍历图中的每一个结点，并按访问的现后顺序将结点输出，以V1作为第一个访问的结点。【输入文件】第一行两个整数m和n，分别表示图的结点数和图中的边数。以下n行表示n条边：每一行两个

18、数x和y，表示x与y之间有一条边。【输出文件】一行：结点的序列。【示例】输入：输出：5 5 1 2 5 3 4 1 2 1 3 2 5 3 5 4 5 第22页，共83页，编辑于2022年，星期五2、广度优先搜索遍历、广度优先搜索遍历 广度优先搜索（广度优先搜索（breadthfirst search）遍历类似树的按层遍历，其过程为：首先访问初始点）遍历类似树的按层遍历，其过程为：首先访问初始点vi,并将其标记为已访问过，接着访问并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点的所有未被访问过的邻接点vi1,vi2,vit并并均标记为已访问过，然后再按照均标记为已访问过，然后再按照v

19、i1,vi2,vit的次序，访问每一个顶点的所有未被的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶有路径相通的顶点都被访问过为止。点都被访问过为止。算法：算法：proc bfs(v)begin setnull(Q);print(v);visitedv:=true;insert(Q,v);repeat h:=delete(Q);for j:=1 to n do if not visitedj and gh,j=1 then begin print(j);visi

20、tedj:=true;insert(Q,j);end;until empty(Q);end;第23页，共83页，编辑于2022年，星期五练习2：无向图的广度优先搜索【问题描述】从文件中读入无向图的信息，按广度优先搜索的方式遍历图中的每一个结点，并按访问的现后顺序将结点输出，以V1作为第一个访问的结点。【输入文件】第一行两个整数m和n，分别表示图的结点数和图中的边数。以下n行表示n条边：每一行两个数x和y，表示x与y之间有一条边。【输出文件】一行：结点的序列。【示例】输入：输出：5 5 1 2 3 5 4 1 2 1 3 2 5 3 5 4 5 第24页，共83页，编辑于2022年，星期五非连通

21、图的遍历非连通图的遍历 前面提到的深度优先遍历和广度优先遍前面提到的深度优先遍历和广度优先遍历都只从图的一个顶点开始进行一次遍历，历都只从图的一个顶点开始进行一次遍历，对于连通图可以遍历到图的所有结点，但对于连通图可以遍历到图的所有结点，但如果图不连通，则有一部分结点无法访问如果图不连通，则有一部分结点无法访问到。修改很简单，每次选取任意一个没有到。修改很简单，每次选取任意一个没有被遍历过的结点开始一次遍历，重复此操被遍历过的结点开始一次遍历，重复此操作直到遍历完图的所有结点即可。作直到遍历完图的所有结点即可。第25页，共83页，编辑于2022年，星期五proc bfs(v)begin set

22、null(Q);print(v);visitedv:=true;flag:=flase;图中顶点是否访问完图中顶点是否访问完 while not flag do begin flag:=true;insert(Q,v);repeat h:=delete(Q);for j:=1 to n do if not visitedj and gh,j=1 then begin print(j);visitedj:=true;insert(Q,j);end;until empty(Q);for j:=1 to n do if visitedj=false then begin v:=j;flag:=fal

23、se;end;end;end;非连通图的遍历第26页，共83页，编辑于2022年，星期五图的连通分量对于连通图只有一个连通分量；对于非连通图有多个连通分量。如右图：有两个连通分量，它们分别是：1，2，34，512345第27页，共83页，编辑于2022年，星期五求连通分量的算法proc bfs(v)begin setnull(Q);print(v);visitedv:=true;flag:=flase;图中顶点是否访问完图中顶点是否访问完 while not flag do begin flag:=true;insert(Q,v);repeat h:=delete(Q);添加操作：将每一个出队

24、的顶点保存；添加操作：将每一个出队的顶点保存；for j:=1 to n do if not visitedj and gh,j=1 then begin print(j);visitedj:=true;insert(Q,j);end;until empty(Q);/repeat.until循环结束一次，得到一个连通循环结束一次，得到一个连通分量；分量；for j:=1 to n do if visitedj=false then begin v:=j;flag:=false;end;end;end;第28页，共83页，编辑于2022年，星期五练习3：求无向图的连通分量【问题描述】从文件中读入

25、无向图的信息，求出该图的连通分量个数。【输入文件】第一行两个整数m和n，分别表示图的结点数和图中的边数。以下n行表示n条边：每一行两个数x和y，表示x与y之间有一条边。【输出文件】输出一个整数，表示连通分量的个数。【示例】输入：输出：5 5 2 1 2 1 3 2 5 3 5 2 3第29页，共83页，编辑于2022年，星期五有向图的强连通图分量定义：在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected

26、components)。下图中，子图1,2,3,4为一个强连通分量，因为顶点1,2,3,4两两可达。5,6也分别是两个强连通分量。第30页，共83页，编辑于2022年，星期五Tarjan算法 Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出：Low(u)=Min DFN(u),Low(v),(u,v)为树枝边，u为v的父节点 DFN(v)

27、,(u,v)为指向栈中节点的后向边(非横叉边)指向其祖先的边 横叉边-从一个连通分量到另一个连通分量之间的边 当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量（当前递归栈内存在一个SCC）。第31页，共83页，编辑于2022年，星期五算法伪代码如下：tarjan(u)DFNu=Lowu=+Index /为节点u设定次序编号和Low初值Stack.push(u)/将节点u压入栈中for each(u,v)in E /枚举每一条边if(v is not visted)/如果节点v未被访问过-说明是树枝tarjan(v)/继续向下找Lowu=min(Lowu,Lowv)e

28、lse if(v in S)/如果节点v还在栈内说明是后向边Lowu=min(Lowu,DFNv)/if(v is visted and v not in S)-(u,v)是横叉边if(DFNu=Lowu)/如果节点u是强连通分量的根repeatv=S.pop /将v退栈，为该强连通分量中一个顶点print vuntil(u=v)第32页，共83页，编辑于2022年，星期五算法流程的演示：从节点1开始DFS，把遍历到的节点加入栈中。搜索到节点u=6时，DFN6=LOW6，找到了一个强连通分量。退栈到u=v为止，6为一个强连通分量。返回节点5，发现DFN5=LOW5，退栈后5为一个强连通分量。第

29、33页，共83页，编辑于2022年，星期五返回节点3，继续搜索到节点4，把4加入堆栈。发现节点4向节点1有后向边，节点1还在栈中，所以LOW4=1。节点6已经出栈，(4,6)是横叉边，返回3，(3,4)为树枝边，所以LOW3=LOW4=1。继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以LOW2=DFN4=5。返回1后，发现DFN1=LOW1，把栈中节点全部取出，组成一个连通分量1,3,4,2。运行Tarjan算法的过程中，每个顶点都被访问了一次，且只进出了一次堆栈，每条边也只被访问了一次，所以该算法的时间复杂度为O(N+M)。第34页，共83页，编辑于2022年，星期五每一

30、头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。这种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。【输入文件】第一行两个数N,M。接下来M行，每行两个数A,B，意思是A认为B是受欢迎的（给出的信息有可能重复，即有可能出现多个A,B）【输出文件】一个数，即有多少头牛被所有的牛认为是受欢迎的。【样例输入】3 31 22 12 3【样例输出】1练习练习4：受欢迎的牛：受欢迎的牛第35页，共83页，编辑于2022年，星期五图的生成树与最小生成树图的生成树与最小生成树在

31、一个连通图G中，如果取它的全部顶点和一部分边构成一个子图G，即：若边集E（G）中的边既将图中的所有顶点连通又不形成回路，则称子图G是原图G的一棵生成树。最小生成树：给图中每个边赋一权值，所有生成树中所选择边的权值之和最小的生成树，称之为最小代价生成树，即是最小生成树。第36页，共83页，编辑于2022年，星期五3124566555136462图31245651342图的最小生成树31245655564图的非最小生成树第37页，共83页，编辑于2022年，星期五普里姆算法普里姆算法 假设G=（V，E）是一个具有n个顶点的连通网，T=（U，TE）是G的最小生成树，其中U是T的顶点集，TE是T的边集

32、，U和TE的初值均为空集。算法开始时，首先从V中任取一个顶点（假定取v1），将它并入U中，此时U=v1，然后只要U是V的真子集，就从那些其一个端点已在T中，另一个端点仍在T外的所有边中，找一条最短（即权值最小）边，假定为（vi，vj），其中，并把该边（vi，vj）和顶点vj分别并入T的边集TE和顶点集U，如此进行下去，每次往生成树里并入一个顶点和一条边，直到（n一1）次后就把所有n个顶点都并入到生成树T的顶点集中，此时UV，TE中含有（n一1）条边，T就是最后得到的最小生成树。第38页，共83页，编辑于2022年，星期五普里姆算法的关键之处是：每次如何从生成树T中到T外的所有边中，找出一条最短

33、边。例如，在第k次前，生成树T中已有k个顶点和（k-1）条边，此时T中到T外的所有边数为k（n-k），当然它包括两顶点间没有直接边相连，其权值被看作为“无穷大”的边在内，从如此多的边中查找最短边，其时间复杂性为O（k（n-k），显然是很费时的。是否有一种好的方法能够降低查找最短边的时间复杂性呢？关键问题第39页，共83页，编辑于2022年，星期五方法是：假定在进行第k次前已经保留着从T中到T外每一顶点（共（n-k）个顶点）的各一条最短边，进行第k次时，首先从这（n-k）条最短边中，找出一条最最短的边（它就是从T中到T外的所有边中的最短边），假设为（vi,vj），此步需进行（n-k）次比较；然后

34、把边（vi,vj）和顶点vj分别并入T中的边集TE和顶点集U中，此时T外只有n-（k+1）个顶点，对于其中的每个顶点vt，若（vj,vt）边上的权值小于已保留的从原T中到vt的最短边的权值，则用（vj，vt）修改之，使从T中到T外顶点vt的最短边为（vj，vt），否则原有最短边保持不变，这样，就把第k次后从T中到T外每一顶点vt的各一条最短边都保留下来了。为进行第（k+1）次运算做好了准备，此步需进行（n-k-1）次比较。所以，利用此方法求第k次的最短边共需比较2（n-k）-1次，即时间复杂性为O（n-k）。解决办法第40页，共83页，编辑于2022年，星期五prim算法设一个辅助数组clos

35、edge，以记录从U到V-U具有最小代价的边。数组中的每个元素closedgev是记录类型，包含两个域：closedgev.lowcast=Mincost(u,v)|uU;closedgev.vex存储该边依附的在U中的顶点。第41页，共83页，编辑于2022年，星期五代 码proc mintree_prim(gn:adjmatrix;u0:integer);begin for v:=1 to n do if vu0 then with closedagev do vex:=u0;lowcast:=gnu0,v;closedgeu0.lowcast:=0;并入U集合for i:=1 to n-

36、1 dobegin k:=min(closedge);寻找代价最小的边 write(closedgek.vex,k);第42页，共83页，编辑于2022年，星期五 closedgek.lowcast:=0;并入U集合 for v:=1 to n do if gnk,vclosedgev.lowcast then begin closedgev.lowcast:=gnk,v;closedgev.vex:=k;end;end;end;第43页，共83页，编辑于2022年，星期五练习1：prim算法实现【问题描述】从文件中读入连通带权图的信息，按prim算法求出该图的最小生成树，以V1作为初始结点。

37、【输入文件】第一行两个整数m和n，分别表示图的结点数和图中的边数。以下n行表示n条边：每一行三个数x、y和k，k表示x与y之间边的权值。【输出文件】共m行，第一行：最小生成树的权；以下m-1行表示选取的边，边的第1个结点小于第2个结点，并按结点由小到大输出。【示例】输入：输出：5 7 45 1 2 17 1 4 2 3 30 1 5 1 4 5 2 4 2 4 10 3 5 3 4 24 3 5 7 1 5 23第44页，共83页，编辑于2022年，星期五练习2：Eddy painting Eddy begins to like painting pictures recently,he is

38、 sure of himself to become a painter.Every day Eddy draws pictures in his small room,and he usually puts out his newest pictures to let his friends appreciate.but the result it can be imagined,the friends are not interested in his picture.Eddy feels very puzze,in order to change all friends s view t

39、o his technical of painting pictures,so Eddy creates a problem for the his friends of you.Problem descriptions as follows:Given you some coordinates pionts on a drawing paper,every point links with the ink with the straight line,causes all points finally to link in the same place.How many distants d

40、oes your duty discover the shortest length which the ink draws?Input：The first line contains 0 n=100,the number of point.For each point,a line follows;each following line contains two real numbers indicating the(x,y)coordinates of the point.Input contains multiple test cases.Process to the end of fi

41、le.Output：Your program prints a single real number to two decimal places:the minimum total length of ink lines that can connect all the points.Sample Input：31.0 1.02.0 2.02.0 4.0Sample Output：3.41第45页，共83页，编辑于2022年，星期五 克鲁斯卡尔算法克鲁斯卡尔算法假设G（V，E）是一个具有n个顶点的连通网，T（U，TE）是G的最小生成树，U的初值等于V，即包含有G中的全部顶点，TE的初值为空。此

42、算法的基本思想是，将图G中的边按权值从小到大的顺序依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边，若选取的边使生成树T形成回路，则将其舍弃，如此进行下去，直到TE中包含有n 1条边为止。此时的T即为最小生成树。第46页，共83页，编辑于2022年，星期五克鲁斯卡尔算法的关键之处是：如何判断欲加入的一条边是否与生成树中已选取的边形成回路。这可将各顶点划分为所属集合的方法来解决，每个集合中的顶点表示一个无回路的连通分量。算法开始时，由于生成树的顶点集等于图G的顶点集，边集为空，所以n个顶点分属于n个集合。每个集合中只有一个顶点，表明顶点之问互不连通。关键问题第47页

43、，共83页，编辑于2022年，星期五Kruskal算法proc mintree_krusk(gn:adjmatrix);begin for i:=1 to n do uni:=i;for i:=1 to n-1 do begin minedge(a,b);write(a,b,gna,b);k:=unb;for i:=1 to n do 两个连通分量合并 if uni=k then uni:=una;end;end;proc minedge(var a:integer;var b:integer);用于在剩下的边中选取不再同一连通分量上的最小代价的边，边的结点分别为a和b。为了实现该过程，可以将

44、图中的边生成边结点（包含两个顶点和代价）数组，由小到大排序，然后通过排序后的数组进行处理；un数组：用来记载随着边的加入，各顶点属于哪个连通分量。第48页，共83页，编辑于2022年，星期五练习3：Kruskal算法实现【问题描述】从文件中读入连通带权图的信息，按Kruskal算法求出该图的最小生成树，以V1作为初始结点。【输入文件】第一行两个整数m和n，分别表示图的结点数和图中的边数。以下n行表示n条边：每一行三个数x、y和k，k表示x与y之间边的权值。【输出文件】共m行，第一行：最小生成树的权；以下m-1行表示选取的边，按选取边的权值由小到大输出。【示例】输入：输出：5 7 45 1 2

45、17 1 4 2 3 30 3 5 1 4 5 2 4 2 4 10 1 5 3 4 24 3 5 7 1 5 23第49页，共83页，编辑于2022年，星期五练习4：判断最小生成树是否唯一Given a connected undirected graph,tell if its minimum spanning tree is unique.Definition 1(Spanning Tree):Consider a connected,undirected graph G=(V,E).A spanning tree of G is a subgraph of G,say T=(V,E),

46、with the following properties:1.V=V.2.T is connected and acyclic.Definition 2(Minimum Spanning Tree):Consider an edge-weighted,connected,undirected graph G=(V,E).The minimum spanning tree T=(V,E)of G is the spanning tree that has the smallest total cost.The total cost of T means the sum of the weigh

47、ts on all the edges in E.InputThe first line contains a single integer t(1=t=20),the number of test cases.Each case represents a graph.It begins with a line containing two integers n and m(1=n=100),the number of nodes and edges.Each of the following m lines contains a triple(xi,yi,wi),indicating tha

48、t xi and yi are connected by an edge with weight=wi.For any two nodes,there is at most one edge connecting them.OutputFor each input,if the MST is unique,print the total cost of it,or otherwise print the string Not Unique!.Sample Input23 31 2 12 3 23 1 34 41 2 22 3 23 4 24 1 2Sample Output3Not Uniqu

49、e!第50页，共83页，编辑于2022年，星期五最短路径最短路径由于从一顶点到另一顶点可能存在着多条路径。每条路径上所经过的边数可能不同，即路径长度不同，我们把路径长度最短（即经过的边数最少）的那条路径叫做最短路径，其路径长度叫做最短路径长度或最短距离。求图中一顶点vi到其余各顶点的最短路径和最短距离比较容易，只要从该顶点vi，出发对图进行一次广度优先搜索遍历，在遍历时记下每个结点的层次即可。第51页，共83页，编辑于2022年，星期五若图是带权图（假定权值非负）从源点vi到终点vj的每条路径上的权（它等于该路径上所经边上的权值之和，称为该路径的带权路径长度）可能不同，我们把权值最小的那条路径

50、也称做最短路径，其权值也称作最短路径长度或最短距离。实际上，这两类最短路径问题可合并为一类，这只要把第一类的每条边的权都设为1就归属于第二类了，所以在以后的讨论中，若不特别指明，均是指第二类的最短路径问题。第52页，共83页，编辑于2022年，星期五求图的最短路径问题包括两个子问题：一是求图中一顶点到其余各顶点的最短路径，二是求图中每对顶点之间的最短路径。下面分别进行讨论。解决问题第53页，共83页，编辑于2022年，星期五 从一顶点到其余各顶点的最短路径迪杰斯特拉（Dijkstra）于1959年提出了解决此问题的一般算法，具体做法是按照从源点到其余每一顶点的最短路径长度的升序依次求出从源点到