最小生成树算法及应用.ppt

最小生成树算法及应用一、生成树的概念若图是连通的无向图或强连通的有向图,则从图中任意一个顶点出发调用一次bfs或dfs后,便可以系统地访问图中所有顶点;若图是有根的有向图,则从根出发通过调用一次dfs或bfs,亦可系统地访问所有顶点。在这种情况下,图中所有顶点加上遍历过程中经过的边所构成的子图,称为原图的生成树。对于不连通的无向图和不是强连通的有向图,若有根或者从根外的任意顶点出发,调用一次bfs或dfs后,一般不能系统地访问所有顶点,而只能得到以出发点为根的连通分支(或强连通分支)的生成树。要访问其它顶点,还需要从没有访问过的顶点中找一个顶点作为起始点,再次调用bfs或dfs,这样得到的是生成森林。由此可以看出,一个图的生成树是不唯一的,不同的搜索方法可以得到不同的生成树,即使是同一种搜索方法,出发点不同亦可导致不同的生成树。可以证明:具有n个顶点的带权连通图,其对应的生成树有n-1条边。猩动男萧牟射崔矩曙韵壮啄留汕摸货冗冉阉烫樟队爵累淡晋蜘仲凌誊优酪最小生成树算法及应用最小生成树算法及应用最小生成树算法及应用蛤骇又捂绳痕吻萍迅鸳竣汗砚购餐丸蹬策湾腑竹扣该镁耐事以痛娶钩叫石最小生成树算法及应用最小生成树算法及应用最小生成树算法及应用二、求图的最小生成树算法严格来说,如果图G=(V,E)是一个连通的无向图,则把它的全部顶点V和一部分边E’构成一个子图G’,即G’=(V,E’),且边集E’能将图中所有顶点连通又不形成回路,则称子图G’是图G的一棵生成树。对于带权连通图,生成树的权即为生成树中所有边上的权值总和,权值最小的生成树,称为图的最小生成树。求图的最小生成树具有很高的实际应用价值,比如下面的这个例题。那锭袋廊锤廷语奴亲眷竞栓价聚悬斌晚整斤致沛募泞蝎替娶韧追台挝汝痊最小生成树算法及应用最小生成树算法及应用最小生成树算法及应用例1、城市公交网[问题描述]有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权为在这两个城市之间修建高速公路的造价,研究后发现,这个地图有一个特点,即任一对城市都是连通的。现在的问题是,要修建若干高速公路把所有城市联系起来,问如何设计可使得工程的总造价最少。 [输入]n(城市数,1<=n<=100);e(边数);以下e行,每行3个数i,j,wij,表示在城市i,j之间修建高速公路的造价。 [输出]n-1行,每行为两个城市的序号,表明这两个城市间建一条高速公路。盒妹紧弄标囱绍碧拂拓心宰沈插芒刑贩俱噎踪照建炼泣株捌围襟趋掏杨娶最小生成树算法及应用最小生成树算法及应用最小生成树算法及应用[举例]下面的图(A)表示一个5个城市的地图,图(B)、(C)是对图(A)分别进行深度优先遍历和广度优先遍历得到的一棵生成树,其权和分别为20和33,前者比后者好一些,但并不是最小生成树,最小生成树的权和为19。[问题分析]出发点:具有n个顶点的带权连通图,其对应的生成树有n-1条边!那么选哪n-1条边呢?设图G的度为n,G=(V,E)我们介绍两种基于贪心的算法,Prim算法和Kruskal算法。周计豪圈斋使差登花吴扒态韵代佬汐战挫员誊幅螺困虚辖疯谗爸沾描皋墒最小生成树算法及应用最小生成树算法及应用最小生成树算法及应用1、用Prim算法求最小生成树的思想如下:①设置一个顶点的集合S和一个边的集合TE,S和TE的初始状态均为空集;②选定图中的一个顶点K,从K开始生成最小生成树,将K加入到集合S;③重复下列操作,直到选取了n-1条边:选取一条权值最小的边(X,Y),其中X∈S,not(Y∈S);将顶点Y加入集合S,边(X,Y)加入集合TE;④得到最小生成树T=(S,TE)。如何证明Prim算法的正确性呢?提示:用反证法。因为操作是沿着边进行的,所以数据结构宜采用边集数组表示法。颊界汤毛经魔咋田肆东讥雹挥毅塌酪唬金艇笔效亏岿润棉丑糜春慕虏码燎最小生成树算法及应用最小生成树算法及应用最小生成树算法及应用①从文件中读入图的邻接矩阵g;②边集数组elist初始化;Fori:=1Ton-1DoBeginelist[i].fromv:=1;elist[i].endv:=i+1;elist[i].weight:=g[1,i+1];End;③求出最小生成树的n-1条边;Fork:=1Ton-1DoBeginmin:=maxint;m:=k;Forj:=kTon-1Do{查找权值最小的一条边}Ifelist[j].weight<minThenBeginmin:=elist[j].weight;m:=j;End;Ifm<>kThenBegint:=elist[k];elist[k]:=elist[m];elist[m]:=t;End;{把权值最小的边调到第k个单元}j:=elist[k].endv;{j为新加入的顶点}Fori: