Primf及Krusf最小成树及matlab源代码

1五树与生成树树是一种特殊的图,它是图论中重要的概念之一,它有着广泛的应用.在计算机科学中有如判定树、语法树、分类树、搜索树、目录树等等.一.树(Tree)1.树的定义:一个连通无回路的无向图T,称之为树.如(a)(a)(b)4.森林:一个无向图的每个连通分支都是树.如(b)2.叶结点:度数为1的结点,称为叶结点.3.分支结点(内结点):度数大于1的结点.25.与树定义等价的几个命题定理给定图T,以下关于树的定义是等价的。⑴无回路的连通图。⑵无回路且e=v-1其中e是T的边数,v是T的结点数。⑶连通的且e=v-1。⑷无回路但添加一条新边则得到一条仅有的回路。⑸连通的,但删去任一条边,T便不连通。⑹每对结点之间有一条且仅有一条路。3二.生成树(支撑树)在图论的应用中,找出一个连通图的所有不同的生成树,以及找出最小生成树是很有意义的.1.定义:如果图G的生成子图是树,则称此树为G的生成树.2.弦:图G中,不在其生成树里的边,称作弦.所有弦的集合,称为该生成树的补.定理连通图至少有一棵生成树.v1v5v4v2v34三.赋权图的最小生成树1.定义:一棵生成树中的所有边的权之和称为该生成树的权.具有最小权的生成树,称为最小生成树.最小生成树很有实际应用价值.例如结点是城市名,边的权表示两个城市间的距离,从一个城市出发走遍各个城市,如何选择最优的旅行路线.又如城市间的通信网络问题,如何布线,使得总的线路长度最短.例如:右图所示2.求最小生成树算法---Kruskal算法:(避圈法)v1v5v4v2v3v8v6v7122137724866534435Kruskal算法思想：在不形成圈得条件下，优先挑选权小的边形成生成树。76788334245v1v2v3v4v5v6v7683324v1v2v3v4v5v6v7数学建模-图论四、最小生成树问题及其算法6。，，取，成的边按权非减次序排列将图1|)|,,2,1()(,,,)1(1||21kVjjvlEeeeGjiiiE。；否，取，转是，取是否相等？、的标号、连结的二点边}{)2(1)()()2(11kkiieEEkkvlulvue。，令的对一切满足)}(,)(min{)()}(,)(max{)()3(vlulvlvvlulvljjj。，转取算法终止；否是)2(1,,?1||)4(1kkVE注：算法构造的最小生成树的边集为E1；标号l具有性质：当且仅当u、v之间有一条仅由E1中的边形成的路时，l(u)=l(v)，因此在步骤(2)发现l(u)=l(v)时，(u,v)不能放入E1，否则会形成一个圈。数学建模-图论四、最小生成树问题及其算法71v2v3v4v5v64686865505061456054例：利用Kruskal算法求出如图G的最小生成树：四、最小生成树问题及其算法数学建模-图论8Kruskal算法Matlab程序如下：functionT=Krusf(d,flag)ifnargin==1n=size(d,2);m=sum(sum(d~=0))/2;b=zeros(3,m);k=1;fori=1:nforj=(i+1):nifd(i.j)~=0b(1,k)=i;b(2,k)=j;b(3,k)=d(i.j);k=k+1;endendendelseb=d;endn=max(max(b(1:2,:)));m=size(b,2);[B,i]=sortrows(b',3);B=B';82020年1月24日四、最小生成树问题及其算法数学建模-图论9c=0;T=[];k=1;t=1:n;fori=1:mift(B(1,i))~=t(B(2,i))T(1:2,k)=B(1:2,i);c=c+B(3,i);k=k+1;tmin=min(t(B(1,i)),t(B(2,i)));tmax=max(t(B(1,i)),t(B(2,i)));forj=1:nift(j)==tmaxt(j)=tmin;endendendifk==nbreak;endendTc92020年1月24日四、最小生成树问题及其算法数学建模-图论10102020年1月24日四、最小生成树问题及其算法数学建模-图论运行结果如下：T=135163266674c=26上述例题的matlab程序如下：b=[11223334556;26364677677;24458378376];Krusf(b,1);112233345562636467767724458378376b76788334245v1v2v3v4v5v6v7683324v1v2v3v4v5v6v711求最小生成树的Prim算法的思想如下：从连通图G=V,E的某一顶点v出发，选择与其关联的具有最小权的边(u0,v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中而另一顶点不在U中的各条边中选择权值最小的边（u，v），把它的顶点加入到集合U中，如此下去，直到图中的所有顶点都加入到生成树顶点集合U中为止，这时得到一颗最小生成树。112020年1月24日四、最小生成树问题及其算法数学建模-图论12例、一个乡有7个自然村，其间道路如图所示，要以村为中心建有线广播网络，如要求沿道路架设广播线，应如何架设？abcdegf141827168213ae12dcb7gf19513Prim算法Matlab程序如下：functionT=Primf(a)l=length(a);a(a==0)=inf;k=1:l;listV(k)=0;listV(1)=1;e=1;while(el)min=inf;fori=1:liflistV(i)==1forj=1:liflistV(j)==0&mina(i,j)min=a(i,j);b=a(i,j);s=i;d=j;endendendend132020年1月24日四、最小生成树问题及其算法数学建模-图论14listV(d)=1;distance(e)=b;source(e)=s;destination(e)=d;e=e+1;endT=[source;destination];forg=1:e-1c(g)=a(T(1,g),T(2,g));endTc142020年1月24日四、最小生成树问题及其算法数学建模-图论15上述例题的Matlab程序如下：a=[02infinfinf4inf;204infinf5inf;inf408inf37;infinf80infinf8;infinfinfinf037;453inf306;infinf78760];%权矩阵Primf(a);152020年1月24日四、最小生成树问题及其算法数学建模-图论运行结果如下：T=116663263574c=24336806787603354730808738045402420A76788334245v1v2v3v4v5v6v7