图论-数学建模（课堂PPT）

1、1 引言引言 图论起源于图论起源于1818世纪。第一篇图论论文是瑞士世纪。第一篇图论论文是瑞士数学家欧拉于数学家欧拉于1736 1736 年发表的年发表的“哥尼斯堡的七座哥尼斯堡的七座桥桥”。 图论中所谓的图论中所谓的“图图”是指是指某类具体事物和这某类具体事物和这些事物之间的联系些事物之间的联系。如果我们用。如果我们用点点表示这些表示这些具体具体事物事物，用连接两点的，用连接两点的线段线段（直的或曲的）表示两（直的或曲的）表示两个个事物的特定的联系事物的特定的联系，就得到了描述这个，就得到了描述这个“图图”的几何形象。图论为任何一个包含了一种二元关的几何形象。图论为任何一个包含了一种二元关系

2、的离散系统提供了一个数学模型，借助于图论系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。的概念、理论和方法，可以对该模型求解。 哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来。问题是与河岸联结起来。问题是要从这四块陆地中的任要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。何一块开始通过每一座桥正好一次，再回到起点。 12 当然可以通过试验去尝试解决这个问题，但当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成

3、功。该城居民的任何尝试均未成功。 欧拉为了解决这个问题，采用了建立数学模欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而每一座桥用连接相应两点的一条线来代替，从而得到一个有得到一个有四个四个“点点”，七条，七条“线线”的的“图图”。问题成为问题成为从任一点出发一笔画出七条线再回到起从任一点出发一笔画出七条线再回到起点点。欧拉考察了一般一笔画的结构特点，给出了。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则一笔画的一个判定法则：这个图是连通的，且每这个图是连通的，且每个

4、点都与偶数线相关联，个点都与偶数线相关联，将这个判定法则应用于将这个判定法则应用于七桥问题，得到了七桥问题，得到了“不可能走通不可能走通”的结果，不但的结果，不但彻底解决了这个问题，而且开创了图论研究的先彻底解决了这个问题，而且开创了图论研究的先河。河。3 我们首先通过一些例子来了解网络优化问题。我们首先通过一些例子来了解网络优化问题。例例1 1 最短路问题最短路问题（SPPSPPshortest path problemshortest path problem） 一名货柜车司机奉命在最短的时间内将一车货物一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交从

5、甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最这一问题相当于需要找到一条从甲地到乙地的最短路。短路。例例2 2 公路连接问题公路连接问题 某一地区有若干个主要城市，现准备修建高速公某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。市都可以经高速公路直接或间接到达另一个城市。假

6、定已经知道了任意两个城市之间修建高速公路假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？公路，使得总成本最小？4例例3 3 指派问题指派问题（assignment problemassignment problem） 一家公司经理准备安排名员工去完成项任务，一家公司经理准备安排名员工去完成项任务， 每人一项。由于各员工的特点不同，不同的员每人一项。由于各员工的特点不同，不同的员 工去完成同一项任务时所获得的回报是不同的。工去完成同一项任务时所获得的回报是不同的。 如何分配工作方案可以使总回报最大

7、？如何分配工作方案可以使总回报最大？例例4 4 中国邮递员问题中国邮递员问题（CPPCPPchinese postman chinese postman problem problem） 一名邮递员负责投递某个街区的邮件。如何为他一名邮递员负责投递某个街区的邮件。如何为他 （她）设计一条最短的投递路线（从邮局出发，（她）设计一条最短的投递路线（从邮局出发， 经过投递区内每条街道至少一次，最后返回邮局）经过投递区内每条街道至少一次，最后返回邮局） ？由于这一问题是我国管梅谷教授？由于这一问题是我国管梅谷教授19601960年首先年首先 提的，所以国际上称之为中国邮递员问题。提的，所以国际上称之为

8、中国邮递员问题。5 例例5 5 运输问题运输问题（transportation problemtransportation problem） 某种原材料有个产地，现在需要将原材料从产地某种原材料有个产地，现在需要将原材料从产地运往个使用这些原材料的工厂。假定个产地的产运往个使用这些原材料的工厂。假定个产地的产量和家工厂的需要量已知，单位产品从任一产地量和家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？可以使总运输成本最低？ 上述问题有两个共同的特点：上述问题有两个共同的特点：一是一是它们的目的都它们

9、的目的都是从若干可能的安排或方案中寻求某种意义下的是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化最优安排或方案，数学上把这种问题称为最优化或优化（或优化（optimizationoptimization）问题；）问题；二是二是它们都易于它们都易于用图形的形式直观地描述和表达，数学上把这种用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（与图相关的结构称为网络（networknetwork）。与图和网）。与图和网络相关的最优化问题就是网络最优化或称网络优络相关的最优化问题就是网络最优化或称网络优化化 （netwok optimizationn

10、etwok optimization）问题。）问题。 62 图与网络的基本概念图与网络的基本概念 2.1 2.1 无向图无向图 一个无向图一个无向图(undirected graph)(undirected graph)是由一个非空有限是由一个非空有限集合集合 和和 中某些元素的无序对集合中某些元素的无序对集合 构构成的二元组，记为成的二元组，记为 。 其中其中 称为称为图的顶点集图的顶点集（vertex vertex setset）或节点集（）或节点集（node setnode set），）， 中的每一个元素中的每一个元素 称为该图的一个顶点（称为该图的一个顶点（vertexvertex）或

11、节）或节点（点（nodenode）；）； 称为称为图的边集图的边集 （edge setedge set），）， 中的每一个元素中的每一个元素 记为记为 或或 ，被称为，被称为该图的一条从该图的一条从 到到 的边（的边（edgeedge）)(GV)(GV)(GE)(),(GEGVG ,)(21nvvvGV)(GV), 2 , 1(nivi,)(21meeeGE)(GEke),(jikvve ijjikvvvve), 2 , 1(mkivjv7 一个图称为一个图称为有限图有限图，如果它的顶点集和边集都有，如果它的顶点集和边集都有 限。图的顶点数用符号限。图的顶点数用符号 或或 表示，边数用表示，边

12、数用 或或 表示。表示。 当讨论的图只有一个时，总是用当讨论的图只有一个时，总是用G G来表示这个图。来表示这个图。从而在图论符号中我们常略去字母从而在图论符号中我们常略去字母G G，例如，例如: :分别分别用用 代替代替 。 端点重合为一点的边称为端点重合为一点的边称为环环(loop)(loop)。 一个图称为一个图称为简单图简单图(simple graph)(simple graph)，如果它既没，如果它既没有环也没有两条边连接同一对顶点。有环也没有两条边连接同一对顶点。|V)(G| E)(G,EV)(),(),(GGEGV8 2.2 2.2 有向图有向图 定义定义 一个有向图（一个有向图

13、（directed graphdirected graph或或 digraphdigraph）G G是由一个非空有限集合是由一个非空有限集合V V和和V V中某些元素的有序对中某些元素的有序对集合构成的二元组，记为集合构成的二元组，记为 其中其中 称为图的称为图的顶点集或节点集顶点集或节点集 . . 称为图的称为图的弧集弧集（arc setarc set），），A A中中的每一个元素的每一个元素( (即中某两个元素的有序对即中某两个元素的有序对) ) 记为记为 或或 ， 当弧当弧 时，时， 称为尾（称为尾（tailtail），）， 为头为头（headhead）. .),(AVG ,21nvvv

14、V,21maaaA),(jikvva ), 2 , 1(nkvvajikjikvva ivjv9 2.3 2.3 完全图、二分图完全图、二分图 每一对不同的顶点都有一条边相连的简单图称为每一对不同的顶点都有一条边相连的简单图称为完全图完全图(complete graph)(complete graph)。n n个顶点的完全图记个顶点的完全图记为为 。 若若 ， ， （这里（这里 表示集合表示集合X X中的元素个数），中的元素个数），X X中无相邻顶点对，中无相邻顶点对，Y Y中亦然，则称中亦然，则称G G为为二分图二分图(bipartite graph)(bipartite graph)；特；

15、特别地，若别地，若 ，则，则 ，则，则称称G G为为完全二分图完全二分图，记成，记成 。 nKYXGV)(YX 0|YX| XYyXx,)(GExy | |,|YXK102.4 2.4 子图子图 如果如果 , , ,图图H H叫做图叫做图G G的子的子图（图（subgraphsubgraph），记作），记作 。若。若H H是是G G的子图，的子图，则则G G称为称为H H的母图。的母图。2.5 2.5 顶点的度顶点的度 设设 ，G G中与中与v v关联的边数（每个环算作两关联的边数（每个环算作两条边）称为条边）称为v v的度的度(degree)(degree)，记作，记作 。若。若 是奇数，称

16、是奇数，称v v是奇顶点是奇顶点(odd point)(odd point)；若是偶数，；若是偶数，称称v v是偶顶点是偶顶点(even point)(even point)。关于顶点的度，我们。关于顶点的度，我们有如下结果：有如下结果：(i) (i) (ii) (ii) 任意一个图的奇顶点的个数是偶数任意一个图的奇顶点的个数是偶数。)()(GVHV)()(GEHEGH )(GVv)(vd)(vdVvvd2)(112.6 2.6 图与网络的数据结构图与网络的数据结构 网络优化研究的是网络上的各种优化模型与算网络优化研究的是网络上的各种优化模型与算法为了在计算机上实现网络优化的算法，首先法为了在

17、计算机上实现网络优化的算法，首先我们必须有一种方法（即数据结构）在计算机上我们必须有一种方法（即数据结构）在计算机上来描述图与网络。来描述图与网络。 这里我们介绍计算机上用来描述图与网络的这里我们介绍计算机上用来描述图与网络的5 5种常种常用表示方法：用表示方法：邻接矩阵表示法、关联矩阵表示法、邻接矩阵表示法、关联矩阵表示法、弧表表示法、邻接表表示法和星形表示法。弧表表示法、邻接表表示法和星形表示法。 在下面数据结构的讨论中，我们首先假设在下面数据结构的讨论中，我们首先假设 是一个简单有向图是一个简单有向图 ， ，并假设，并假设V中的中的顶点用自然数顶点用自然数1,2,n表示或编号，表示或编号

18、，A中的弧用自中的弧用自然数然数1,2,m表示或编号。表示或编号。 ),(AVG mAnV| ,|12（i）邻接矩阵表示法）邻接矩阵表示法 邻接矩阵表示法是将图以邻接矩阵（邻接矩阵表示法是将图以邻接矩阵（adjacency adjacency matrixmatrix）的形式存储在计算机中。图）的形式存储在计算机中。图 的的邻接矩阵是如下定义的：邻接矩阵是如下定义的：C C是一个是一个n n* *n n的的0-10-1矩阵，矩阵，即即 也就是说，如果两节点之间有一条弧，则邻接矩也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为阵中对应的元素为1 1；否则为；否则为0 0。 ),(AVG

19、 nnnnijcC1 , 0)(.),(, 0,),(, 1AjiAjicij13 例例1 1 对于所示的图，可以用邻接矩阵表示为对于所示的图，可以用邻接矩阵表示为 同样，对于网络中的权，也可以用类似邻接矩阵同样，对于网络中的权，也可以用类似邻接矩阵的矩阵表示。只是此时一条弧所对应的元素不再的矩阵表示。只是此时一条弧所对应的元素不再是是1 1，而是，而是相应的权相应的权而已。如果网络中每条弧赋有而已。如果网络中每条弧赋有多种权，则可以用多个矩阵表示这些权。多种权，则可以用多个矩阵表示这些权。011001010000010010000011014（iiii）关联矩阵表示法）关联矩阵表示法 关联矩

20、阵表示法是将图以关联矩阵（关联矩阵表示法是将图以关联矩阵（incidence incidence matrixmatrix）的形式存储在计算机中）的形式存储在计算机中 图图 的关联矩阵的关联矩阵B B是如下定义的：是如下定义的：B B是一是一个个n n* *m m的矩阵，即的矩阵，即),(AVG mnmnikbB1 , 0 , 1)(., 0,),(, , 1,),(, 1其它AijkVjAjikVjbik15 如果一个节点是一条弧的如果一个节点是一条弧的起点起点，则关联矩阵中对，则关联矩阵中对应的元素为应的元素为1 1；如果一个节点是一条弧的；如果一个节点是一条弧的终点终点，则，则关联矩阵中

21、对应的元素为关联矩阵中对应的元素为-1-1；如果一个节点与一；如果一个节点与一条弧条弧不关联不关联，则关联矩阵中对应的元素为，则关联矩阵中对应的元素为0 0。 例例2 2 对于例对于例1 1所示的图，如果关联矩阵中每列对应所示的图，如果关联矩阵中每列对应弧的顺序为弧的顺序为(1,2)(1,2)，(1,3)(1,3)，(2,4)(2,4)，(3,2)(3,2)，(4,3)(4,3)，(4,5)(4,5)，(5,3)(5,3)和和(5,4)(5,4)，则关联矩阵表示，则关联矩阵表示为为（列单位为弧）（列单位为弧） 111000001011010001011010000011010000001116

22、（iiiiii）弧表示法）弧表示法 弧表表示法将图以弧表（弧表表示法将图以弧表（arc listarc list）的形式存储）的形式存储在计算机中。所谓图的弧表，也就是图的弧集合在计算机中。所谓图的弧表，也就是图的弧集合中的所有有序对。中的所有有序对。 例例3 3，假设弧，假设弧(1,2)(1,2)，(1,3)(1,3)，(2,4)(2,4)，(3,2)(3,2)，(4,3)(4,3)，(4,5)(4,5)，(5,3)(5,3)和和(5,4)(5,4)上的权分别为上的权分别为8 8，9 9，6 6，4 4，0 0，3 3，6 6和和7 7，则弧表表示如下：，则弧表表示如下： 起点起点11234

23、455终点终点23423534权权8964036717（iviv）邻接表表示法）邻接表表示法 邻接表表示法将图以邻接表（邻接表表示法将图以邻接表（adjacency listsadjacency lists）的形式存储在计算机中。的形式存储在计算机中。 所谓图的邻接表，也就是图的所有节点的邻接表所谓图的邻接表，也就是图的所有节点的邻接表的集合；的集合；而对每个节点，它的邻接表就是它的所而对每个节点，它的邻接表就是它的所有出弧有出弧。邻接表表示法就是对图的每个节点，用。邻接表表示法就是对图的每个节点，用一个单向链表列出从该节点出发的所有弧，链表一个单向链表列出从该节点出发的所有弧，链表中每个单元

24、对应于一条出弧。中每个单元对应于一条出弧。为了记录弧上的权，为了记录弧上的权，链表中每个单元除列出弧的另一个端点外，还可链表中每个单元除列出弧的另一个端点外，还可以包含弧上的权等作为数据域以包含弧上的权等作为数据域。图的整个邻接表。图的整个邻接表可以用一个指针数组表示。可以用一个指针数组表示。 18 对于有向图对于有向图 ，一般用，一般用 表示节表示节点的邻接表，即节点的所有出弧构成的集合或链点的邻接表，即节点的所有出弧构成的集合或链表（实际上只需要列出弧的另一个端点，即弧的表（实际上只需要列出弧的另一个端点，即弧的头）。例如上面例子，头）。例如上面例子， ， 等。等。),(AVG )(iA3

25、 , 2) 1 (A4 , 3)5(A19（v v）星形表示法）星形表示法 星形（星形（starstar）表示法的思想与邻接表表示法的思）表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点，它也是记录想有一定的相似之处。对每个节点，它也是记录从该节点出发的所有弧，但它不是采用单向链表从该节点出发的所有弧，但它不是采用单向链表而是采用一个单一的数组表示。而是采用一个单一的数组表示。 记录弧信息的数组弧编号12345678起点11234455终点23423534权89640367203 应用应用最短路问题最短路问题 3.1 3.1 两个指定顶点之间的最短路径两个指定顶点之间的最短路径 问

26、题如下：给出了一个连接若干个城镇的铁路网问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短络，在这个网络的两个指定城镇间，找一条最短铁路线。铁路线。 以各城镇为图以各城镇为图G G的顶点，两城镇间的直通铁路为图的顶点，两城镇间的直通铁路为图G G相应两顶点间的边，得图相应两顶点间的边，得图G G。对。对G G的每一边的每一边e e，赋，赋以一个实数以一个实数 直通铁路的长度，称为直通铁路的长度，称为e e的权，的权，得到赋权图得到赋权图G G。G G的子图的权是指子图的子图的权是指子图G G的各边的权的各边的权和。和。 问题就是求赋权图中指定的两个顶点问题就是

27、求赋权图中指定的两个顶点 间的具间的具最小权的轨。这条轨叫做最小权的轨。这条轨叫做 间的最短路，它间的最短路，它的权叫做的权叫做 间的距离，亦记作间的距离，亦记作 。)(ew00,vu00,vu00,vu),(00vud21求最短路已有成熟的算法：求最短路已有成熟的算法：迪克斯特拉迪克斯特拉（DijkstraDijkstra）算法，其基本思想是按距算法，其基本思想是按距 从近到远为顺序，依次从近到远为顺序，依次求得求得 到的到的G G各顶点的最短路和距离，直至（或直各顶点的最短路和距离，直至（或直至的所有顶点），算法结束。为避免重复并保留每至的所有顶点），算法结束。为避免重复并保留每一步的计算

28、信息，采用了标号算法。下面是该算法一步的计算信息，采用了标号算法。下面是该算法。(i)(i) 令令 ，对，对 令令 ， ， 。(ii) (ii) 对每个对每个 , ,用用 代替代替 计算计算 ，把达到这个最小值的一个顶点，把达到这个最小值的一个顶点 记为记为 ，令，令 。(iii)(iii)若若 ，停止；若，停止；若 ，用，用i+1i+1代替代替 i i，转，转(ii)(ii)。0u0u0)(0ul0uv )(vl00uS 0iiSv)()(),(minuvwulvliSu)(vl)(minvliSv1iu11iiiuSS1| Vi1| Vi22找出找出u0u0到其他各点的最短路径到其他各点的

29、最短路径23243.2 每对顶点之间的最短路径每对顶点之间的最短路径 计算赋权图中各对顶点之间最短路径，显然可以计算赋权图中各对顶点之间最短路径，显然可以调用调用DijkstraDijkstra算法。具体方法是：算法。具体方法是：每次以不同的每次以不同的顶点作为起点顶点作为起点，用，用DijkstraDijkstra算法求出从该起点到算法求出从该起点到其余顶点的最短路径，反复执行次这样的操作，其余顶点的最短路径，反复执行次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。就可得到从每一个顶点到其它顶点的最短路径。 第二种解决这一问题的方法是由第二种解决这一问题的方法是由Floyd R WF

30、loyd R W提出的提出的算法，称之为算法，称之为FloydFloyd算法。算法。 25假设图权的邻接矩阵为，假设图权的邻接矩阵为，来存放各边长度，其中：来存放各边长度，其中： ； 之间没有边，在程序中以各边都不之间没有边，在程序中以各边都不 可能达到的充分大的数代替；可能达到的充分大的数代替； 是是 i,ji,j之间边的长度，之间边的长度， 。nnnnnnaaaaaaaaaA21222211121100iiani, 2 , 1ijaji,ijijwa nji, 2 , 1,26 FloydFloyd算法的基本思想是：递推产生一个矩阵序算法的基本思想是：递推产生一个矩阵序列列 ，其中，其中

31、表示从顶点表示从顶点 到顶点到顶点 的路径上所经过的顶点序号不大于的路径上所经过的顶点序号不大于k k 的最短路径长度。的最短路径长度。 计算时用迭代公式：计算时用迭代公式： k k是迭代次数，是迭代次数， 。 最后，当最后，当k=nk=n时，时， 即是各顶点之间的最短通路值。即是各顶点之间的最短通路值。 ( (例题见附件例题见附件) )nkAAAA,10),(jiAkivjv),(),(),(min(),(111jkAkiAjiAjiAkkkknkji, 2 , 1,nA274 树树4.1 4.1 基本概念基本概念连通的无圈图叫做树，记之为连通的无圈图叫做树，记之为T T。4.2 4.2 应

32、用应用连线问题连线问题 欲修筑连接欲修筑连接n n个城市的铁路，已知城与城之间的铁个城市的铁路，已知城与城之间的铁路造价为路造价为 ，设计一个线路图，使总造价最低。，设计一个线路图，使总造价最低。 连线问题的数学模型是在连通赋权图上求权最小连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具有最小权的生成树叫做最小生的生成树。赋权图的具有最小权的生成树叫做最小生成树。成树。 ijC28定理定理 设设G是具有是具有n个顶点的图，则下述命题等价：个顶点的图，则下述命题等价：1) G是树（是树（ G无圈且连通）；无圈且连通）；2) G无圈，且有无圈，且有n-1条边；条边；3) G连通，且有

33、连通，且有n-1条边；条边；4) G无圈，但添加任一条新边恰好产生一个圈无圈，但添加任一条新边恰好产生一个圈; 5) G连通，且删去一条边就不连通了（即连通，且删去一条边就不连通了（即G为为最最最小连通图最小连通图）；）；6) G中任意两顶点间有唯一一条路中任意两顶点间有唯一一条路.29找图中生成树的方法找图中生成树的方法可分为两种：避圈法和破圈法可分为两种：避圈法和破圈法 A 避圈法避圈法 : 深探法和广探法深探法和广探法 B 破圈法破圈法 30A 避圈法 这种方法就是在已给的图这种方法就是在已给的图G中，每步选出一中，每步选出一条边使它与已选边不构成圈，直到选够条边使它与已选边不构成圈，直

34、到选够n-1条边为条边为止止. 这种方法可称为这种方法可称为“避圈法避圈法”或或“加边法加边法” 在避圈法中，按照边的选法不同，找图中生在避圈法中，按照边的选法不同，找图中生成树的方法可分为两种：成树的方法可分为两种：深探法深探法和和广探法广探法.31a) 深探法深探法 若这样的边的另一端均已有标号，就退到标号为若这样的边的另一端均已有标号，就退到标号为步骤如下：步骤如下：i) 在点集在点集V中任取一点中任取一点u,ii) 若某点若某点v已得标号，检已得标号，检端是否均已标号端是否均已标号. 若有边若有边vw之之w未标号未标号,则给则给w代代v，重复，重复ii).i-1的的r点点,以以r代代v

35、,重复重复ii),直到全部点得到标号为止直到全部点得到标号为止.给以标号给以标号0.查一端点为查一端点为v的各边，另一的各边，另一w以标号以标号i+1，记下边，记下边vw.令令012345678910111213例例用深探法求出下图用深探法求出下图10的一棵生成树的一棵生成树 32b)广探法广探法步骤如下：步骤如下：i) 在点集在点集V中任取一点中任取一点u,ii) 令所有标号令所有标号i的点集为的点集为是否均已标号是否均已标号. 对所有未标对所有未标号之点均标以号之点均标以i+1,记下这些记下这些 iii) 对标号对标号i+1的点重复步的点重复步步骤步骤ii)，直到全部点得到，直到全部点得到

36、给给u以标号以标号0.Vi,检查检查Vi,VVi中的边端点中的边端点边边.例例用广探法求出下图用广探法求出下图10的一棵生成树的一棵生成树 标号为止标号为止.图103101221321223433B 破圈法破圈法 相对于避圈法，还有一种求生成树的方法叫做相对于避圈法，还有一种求生成树的方法叫做“破圈法破圈法”. . 这种方法就是在图这种方法就是在图G G中任取一个圈，任中任取一个圈，任意舍弃一条边，将这个圈破掉，重复这个步骤直到图意舍弃一条边，将这个圈破掉，重复这个步骤直到图G G中没有圈为止中没有圈为止. .例例 用破圈法求出用破圈法求出 下图的一棵生成树下图的一棵生成树.图的生成树不是唯一

37、的图的生成树不是唯一的 .34A A Kruskal Kruskal算法（或避圈法）算法（或避圈法）步骤如下：步骤如下： 1) 选择边选择边e1，使得，使得w(e1)尽可能小；尽可能小；2) 若已选定边若已选定边 ，则从，则从ieee,.,21,.,21ieeeE中选取中选取 ，使得，使得:1iei) 为无圈图，为无圈图，,.,121ieeeG ii) 是满足是满足i)的尽可能小的权，的尽可能小的权，)(1iew 3) 当第当第2)步不能继续执行时，则停止步不能继续执行时，则停止.定理定理4 由由Kruskal算法构作的任何生成树算法构作的任何生成树,.,121*eeeGT都是最小树都是最小树

38、.最小生成树与算法最小生成树与算法35例例 用用Kruskal算法求下图的最小树算法求下图的最小树.在左图中在左图中 权值权值,.,821eee最小的边有最小的边有 任取一条任取一条 ,51ee,1e 在在 中选取权值中选取权值,.,832eee,5e最小的边最小的边 中权值最小边有中权值最小边有 , 从中选从中选：73,ee;3e任取一条边任取一条边会与已选边构成圈会与已选边构成圈,故停止故停止,得得中选取在中选取中选取在中选取,7e 中选取中选取 . 但但 与与 都都,86ee84,ee4e8e,876432eeeeee,87642eeeee,42ee在36B破圈法破圈法算法算法2 步骤如

39、下：步骤如下： 1) 1) 从图从图G G中任选一棵树中任选一棵树T T1 1. .2) 2) 加上一条弦加上一条弦e e1 1，T T1 1+e+e1 1中中 立即生成一个圈立即生成一个圈. . 去掉此去掉此 圈中最大权边，得到新圈中最大权边，得到新树树T T2 2, ,以以T T2 2代代T T1 1, ,重复重复2)2)再再检查剩余的弦，直到全检查剩余的弦，直到全部弦检查完毕为止部弦检查完毕为止. .例例 用破圈法求下图的最小树用破圈法求下图的最小树.37 prim prim算法构造最小生成树算法构造最小生成树 设置两个集合设置两个集合P P和和Q,Q,其中其中P P用于存放的最小生成用

40、于存放的最小生成树树G G中的顶点，集合中的顶点，集合Q Q存放的最小生成树存放的最小生成树G G中的边。令中的边。令集合集合P P的初值为的初值为 （假设构造最小生成树时，（假设构造最小生成树时，从从顶点顶点 出发），集合出发），集合Q Q的初值为的初值为 。primprim算法的思想是算法的思想是，从所有，从所有 ， 的边的边中，选取具有最小权值的边中，选取具有最小权值的边 ，将顶点，将顶点v v加入加入集合集合P P中，将边中，将边pvpv加入集合加入集合Q Q中，如此不断重复，直中，如此不断重复，直到到 P=V P=V 时，最小生成树构造完毕，这时集合时，最小生成树构造完毕，这时集合Q

41、 Q中包中包含了最小生成树的所有边。含了最小生成树的所有边。1vP 1vQPpPVvpv38例例11 用用prim算法求右图的最小生成树。算法求右图的最小生成树。我们用的第一、二、三行分别表示生成树边的起点、终点、权集合。我们用的第一、二、三行分别表示生成树边的起点、终点、权集合。MatlabMatlab程序如下：程序如下：clc;clear;clc;clear;M=1000;M=1000;a(1,2)=50; a(1,3)=60;a(1,2)=50; a(1,3)=60;a(2,4)=65; a(2,5)=40;a(2,4)=65; a(2,5)=40;a(3,4)=52;a(3,7)=45;a(3,4)=52;a(3,7)=45;a(4,5)=50; a(4,6)=30;a(4,7)=42;