《最小生成树》由会员分享，可在线阅读，更多相关《最小生成树（45页珍藏版）》请在金锄头文库上搜索。
1、,数据结构与算法 第15学时 最小生成树,图的遍历 从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。,深度优先遍历(depth-first search, DFS) 广度优先遍历(breadth-first search, BFS),内容回顾：,主要内容： 生成树的概念 最小生成树 构造最小生成的方法 (难点） 1.普里姆(Prim)算法 (重点) 2.克鲁斯卡尔(Kruskal)算法,图的基本术语,生成树：一个含n个顶点的连通图的生成树是一个极小连通子图。它含有图中全部n个顶点，但只有足以构成一棵树的n-
2、1条边。,最大连通分量的一棵生成树,多一条边会怎样？,少一条边会怎样？,5,生成树说明,一个图可以有许多棵不同的生成树 所有生成树具有以下特点： 生成树是图的极小连通子图 一个有n个顶点的连通图的生成树有n-1条边 在生成树中再加一条边必然形成回路 含n个顶点n-1条边的图不一定是生成树,如果一个图有n个顶点和小于(n-1)条边，则是非连通图。 如果它多于(n-1)条边，则一定有回路。,6,对于一个带权（假定每条边上的权均为大于零的实数)无向连通图G中的不同生成树，其每棵树的所有边上的权值之和也可能不同；图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树。 按照生成树的定义，n个顶点
3、的连通图的生成树有n个顶点、n-1条边。构造最小生成树的准则有三条： （1）必须只使用该图中的边来构造最小生成树； （2）只有n个顶点，n-1条边； （3）不能使用产生回路的边。,最小生成树,7,引入：问题提出,要在n个城市之间建立通信网，要求：建立该通信网花费的总代价最少。 顶点表示城市 权城市间建立通信线路所需花费代价,问题分析,n个城市间，最多可设置n(n-1)/2条线路 n个城市间建立通信网，只需n-1条线路 问题转化为： 如何在可能的线路中选择n-1条，能把 所有城市（顶点）均连起来，且总耗费 （各边权值之和）最小,最小生成树的应用,希望找到一棵生成树，它的每条边上的权值之和最小最小
4、代价生成树,8,最小生成树 普里姆(Prim)算法,算法思想： 1.将图G=(V,E)分为两个顶点集 U已选顶点集; V-U未选顶点集. 2.每次从V-U中选择一个到U中顶点距离最短的顶点;直到所有顶点都被选择.,时间复杂度为o(n2)，其中n为网中顶点的个数。,Prim算法适用于求边稠密的网的最小生成树。,9,0,5,0,4,6,1,3,2,28,10,25,14,24,16,18,12,0,4,6,1,3,2,10,25,5,原图,5,0,4,6,1,3,2,10,25,5,0,4,6,1,3,2,10,25,12,5,0,4,1,3,2,10,25,16,12,5,0,4,6,1,3,2
5、,10,25,14,16,12,例1：应用普里姆(Prim) 算法构造最小生成树,20,20,20,20,20,6,11,课堂练习：,a,a,b,d,a,b,d,a,b,c,d,a,b,c,e,f,d,a,b,c,e,f,f,2,2,2,2,2,1,2,2,1,2,2,1,2,1,1,1,12,最小生成树 克鲁斯卡尔(Kruskal)算法,算法思想： 是一种按权值的递增次序选择合适的 边来构造最小生成树的方法。 1. 边集E按权值递增排序 初始化最小生成树的边集T= 2. 每次从边集E选择权值 最小的边e加入T, 使e和T中的边不能构成环.,1,2,3,4,5,6,13,10,例1：应用克鲁斯
6、卡尔算法构造最小生成树的过程,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,12,5,0,4,6,1,3,2,5,0,4,6,1,3,2,原图 (a) (b),14,10,12,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,12,5,0,4,6,1,3,2,5,0,4,6,1,3,2,10,14,12,原图 (c) (d),5,0,4,6,1,3,2,10,14,16,12,(e) (f) (g),5,0,4,6,1,3,2,10,14,22,16,12,5,0,4,6,1,2,10,25,14,22,16,12,3,15,6,1,4
7、,3,2,5,6,1,4,3,2,5,6,1,4,3,2,5,6,1,4,3,2,5,11,11,12,13,16,课堂练习:,11,12,11,12,13,11,12,14,6,1,4,3,2,5,16,13,11,12,14,第(1)种,第(2)种,16,普里姆（Prim）算法求最小生成树-基于邻接矩阵,17,在构造过程中，设置了两个辅助数组： closest :生成树中的某个顶点。 记录生成树顶点集合外各顶点距离集合内哪个顶点最近(即权值最小)。 lowcost :最小权值。 存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值；,普里姆（Prim）算法求最小生成树,18,辅助
8、数组各分量值的变化,(0,2),(2,5) (5,3),(2,1) (1,4),19,普里姆（Prim）算法如下： #define INF 32767 /INF表示 void Prim(MGraph g,int v) int lowcostMAXV; int min; int closestMAXV,i,j,k; for (i=0;ig.n;i+) /给lowcost和closest置初值 lowcosti=g.edgesvi; closesti=v; ,lowcosti表示顶点i（i VU）到U中所有顶点的最小代价，从顶点i到U中最小代价的顶点用closesti表示。 并规定lowcosti
9、=0表示这个顶点在U中。（i,closesti）构成最小生成树。,i,U,VU,v,lowcosti,closesti,注意：是(i,closesti)构成最小生成树（iv）的一条边，而不是从顶点v来确定的。,一对多的关系,多对一的关系,20,for (i=1;ig.n;i+) /找出(n-1)个顶点 min=INF; for (j=0;jg.n;j+) /在(V-U)中找出离U最近的顶点k if (lowcostj!=0 /标记k已经加入U,j,U,VU,k,lowcosti,closesti=k,从j中找离U中顶点最近的顶点k，然后将k加到U中,21,for (j=0;jg.n;j+) /
10、修改数组lowcost和closest if (g.edgeskj!=0 ,修改U和V-U之间的候选边，即调整,表示顶点k到顶点j有边,局部最优调整全局最优,贪心算法思想,最优结果,22,0,1,2,2,3,1,v=0,lowcost0=0 lowcost1=2 lowcost2=3,0,1,2,2,3,1,closest0=0 closest1=0 closest2=0,lowcost0=0 lowcost1=2 lowcost2=3,closest0=0 closest1=0 closest2=0,修改,lowcost0=0 lowcost1=0 lowcost2=1,closest0=0
11、 closest1=0 closest2=1,最小生成树,(0,0) (0,1) (1,2),示例,Prim()算法中有两重for循环，所以时间复杂度为O(n2)。,23,普里姆算法,克鲁斯卡尔算法,时间复杂度,O(n2),O(elog2e),稠密图,稀疏图,算法名,适应范围,总结：最小生成树两种算法的比较,课堂小结： 生成树的概念 最小生成树 构造最小生成的方法 (难点） 1.普里姆(Prim)算法 (重点) 2.克鲁斯卡尔(Kruskal)算法,课后实践： 对右图采用Prim算法求得最小生成树。,课后作业： 教材P247 T8.2,25,8.5.1 路径的概念 在一个无权的图中，若从一顶点
12、到另一顶点存在着一条路径，则称该路径长度为该路径上所经过的边的数目，它等于该路径上的顶点数减1。 由于从一顶点到另一顶点可能存在着多条路径，每条路径上所经过的边数可能不同，即路径长度不同，我们把路径长度最短（即经过的边数最少）的那条路径叫做最短路径，其路径长度叫做最短路径长度或最短距离。,对于带权的图，考虑路径上各边上的权值，则通常把一条路径上所经边的权值之和定义为该路径的路径长度或称带权路径长度。 从源点到终点可能不止一条路径，把带权路径长度最短的那条路径称为最短路径，其路径长度（权值之和）称为最短路径长度或者最短距离。,8.5 最短路径,26,用带权的有向图表示一个交通运输网，图中： 顶点
13、表示城市 边表示城市间的交通联系 权表示此线路的长度或沿此线路运输所花的时间或费用等 问题：从某顶点出发，到达另一顶点，怎样走使得费用（时间）最少？ 求解：两个顶点存在多条路径，其中各边上权值之和最小的一条路径称为最短路径,其路径长度（权值之和）叫做最短路径长度或最短距离。,最短路径问题的提出,27,狄克斯特拉（Dijkstra）算法: 基本思想是：设G=(V，E)是一个带权有向图， 把图中顶点集合V分成两组： 第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径v，k，就将k加入到集合S中，直到全部顶点都加入到S中，算法就结束了） 第二组为其余未确定最短
14、路径的顶点集合（用U表示）。,单源最短路径,28,按最短路径长度的递增次序依次把U组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。 此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。,29,（1）初始时，S只包含源点即S=v，v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或（若u不是v的出边邻接点）。 （2）从U中选取一个距离v最小的顶点k，把k加入S中（该选定的距离就是v到k的最短路径长度）。
15、 （3）以k为新考虑的中间点，修改U中各顶点的距离：若从源点v到顶点u（uU）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。 （4）重复步骤（2）和（3）直到所有顶点都包含在S中。,狄克斯特拉算法的过程,30,顶点v到j的最小距离MIN(cvk+wkj，cvj),k,v,j,.,cvk,cvj,边wkj,31,0 0,1 0,1,2 0,1,2,3 0,1,2,3,5 0,1,2,3,5,4 0,1,2,3,5,4,6,0, 0, 0, 0, -1, -1, -1 0, 0, 1, 0, 1, -1, -1 0, 0, 1, 0, 1, 2, -1 0, 0, 1, 0, 1, 2, -1 0, 0, 1, 0, 5, 2, 5 0, 0, 1, 0, 5, 2, 4
