资源预览内容
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
第9页 / 共11页
第10页 / 共11页
亲,该文档总共11页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
word离散数学大作业 -最小生成树 某某:陈强 辅导教师:李阳阳一、最小生成树的概念: 给定一个连通图,要求构造具有最小代价的生成树时,也即使生成树各边的权值总和达到最小。把生成树各边的权值总和定义为生成树的权,那么具有最小权值的生成树就构成了连通图的最小生成树,最小生成树可简记为MST。二、构造无向连通图的最小生成树的方法:1. Prim普里姆算法算法: 假设G(V,E)是有n个顶点的无向连通图,用T(U,TE)表示要构造的最小生成树,其中U为顶点集合,TE为边的集合。(1) 初始化:令V= ,TE=。从V中取一个顶点u0放入生成树的顶点集U中,作为第一个顶点,此时T=u0,;(2) 从的边u,v中找一条代价最小的边,将其放入TE中,并将放入U中。(3) 重复步骤2,直至U=V为止。此时TE集合中必有n-1条边,T即为所要构造的最小生成树。特殊处理:如果两个顶点之间没有直接相连的边,权值置为一个max的数 自身和自身的权值置为MAX的值代码:function T=Prim(i,G_dist)%T是返回的最小生成树%i为输入的为最小生成树选定的第一个顶点%G_dist是待输入的数据,是图G边u,v的权值矩阵m,n=size(G_dist);%读入无向图的顶点数目为m=nv=i;%将选定的顶点放入中间变量v中T=zeros(3,m-1);%最小生成树有m-1条边。第一行存放边的起点,第二行存放边的终点,第三行存放边的权值%初始化最小生成树的矩阵for j=1:m-1 T(1,j)=v;%将第一个顶点放入最小生成树的矩阵中if j=v T(2,j)=j+1; T(3,j)=G_dist(v,j+1);else T(2,j)=j; T(3,j)=G_dist(v,j); endend%求第k条边for k=1:(n-1) min=10000;%初始化一个最小的权值%找出最短边,并将最短变的下标记录在mid中for j=k:(n-1)if T(3,j)min min=T(3,j); mid=j;endend e=T(:,mid);T(:,mid)=T(:,k);T(:,k)=e;%将最短的边所在的一列和第k列交换 v=T(2,k);%v中存放新找到的最短边在V-U中的顶点for j=(k+1):(n-1)%修改所存储的最小边集 d=G_dist(v,T(2,j);if dT(3,j) T(3,j)=d;T(1,j)=v;endendendDG=sparse(T(1,:),T(2,:),T(3,:),m,m);%用稀疏矩阵view(biograph(DG,ShowArrows,off,ShowWeights,on);%画图调用函数G=10000,10,3,10000,10000,10000;10,10000,5,8,6,10000;3,5,10000,10000,2,10000;10000,8,10000,10000,7,11;10000,6,2,7,10000,17;10000,10000,10000,11,17,10000;%G表示图G的各边权值,自身到自身的权值和不直接相连的顶点的权值设为10000i=1;T1=1,2,1,3,2,2,4,4,5;3,3,2,5,5,4,5,6,6;3,5,10,2,6,8,7,11,17;0,0,0,0,0,0,0,0,0;%T1表示图G的边的信息,第一行是边的起始点,第二行是边的终点,第三行是边的权重,第四行表示对边的选择T=T1(1:3,:);DG=sparse(T1(1,:),T1(2,:),T1(3,:),m,m);%用稀疏矩阵view(biograph(DG,ShowArrows,off,ShowWeights,on);%画图Prim(i,G);结果:图G:Prim生成的最小生成树:2. Kruskal(克鲁斯卡尔)算法算法: 假设G(V,E)是有n个顶点的无向连通图。1初始化:设置最小生成树的初始状态为只有n个顶点而无任何边的非连通图TV,。2依次选择E中的最小代价边,假如该代价边依附于T中两个不同的连通分量,如此将该边参加TE中。否如此,舍去此边而选择下一条代价最小的边。3重复步骤2直到所有顶点都在同意连通分量上为止。这时T就是G的一棵最小生成树。代码:function T=Kruscal(T1,e,m)%T是返回的最小生成树%T1是图G的边信息%e表示的是图G中的边的数目%m是图G的顶点数目%初始化存放顶点连通信息的矩阵GGGG=zeros(1,m);for i=1:m GG(i)=i;end%j=0;%直到选够m-1条边即可完毕程序%while j=m-1break;endendfor i=1:eif T1(4,i)=2 | T1(4,i)=0 T1(:,i)=0;0;0;0;endendT1=T1(:,any(T1);T=T1(1:3,:);DG=sparse(T1(1,:),T1(2,:),T1(3,:),m,m);%用稀疏矩阵view(biograph(DG,ShowArrows,off,ShowWeights,on);%画图调用函数e=9;%图G的边的数目m=6;%图G的顶点数目T1=1,2,1,3,2,2,4,4,5;3,3,2,5,5,4,5,6,6;3,5,10,2,6,8,7,11,17;0,0,0,0,0,0,0,0,0;%T1表示图G的边的信息,第一行是边的起始点,第二行是边的终点,第三行是边的权重,第四行表示对边的选择T=T1(1:3,:);DG=sparse(T1(1,:),T1(2,:),T1(3,:),m,m);%用稀疏矩阵view(biograph(DG,ShowArrows,off,ShowWeights,on);%画图T1=T1;T1=sortrows(T1,3);%将T1的转置按照权值生序排列T1=T1;%转置回来Kruscal(T1,e,m);结果:图G:Kruscal最小生成树:文案大全
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号